Volatility

Definition

Let [math]p \in [0,1][/math] and [math]X(t) \in \{-1,1\}^n[/math] be a continuous-time Markov process where each entry [math]X_i(t)[/math] jumps from 0 to 1 with rate [math]p[/math], from 1 to 0 with rate [math]1-p[/math], and is independent of everything else. We assume that X(0) starts at the stationary measure, i.e is 1 with probability [math]p[/math] and 0 with probability [math]1-p[/math]. Given a Boolean function [math]f:\{-1,1\}^n \to \{-1,1\}[/math], we can count how many times the continuous-time process [math]f(X(t))[/math] changes sign during the interval [math]t\in[0,1][/math]. Denote this number by C.

A sequence of Boolean functions [math]f_n[/math] is said to be volatile if [math]C_n \to \infty[/math] in distribution.

A sequence of Boolean functions [math]f_n[/math] is said to be tame if [math]C_n[/math] is tight (i.e for every [math]\varepsilon \gt 0[/math], there is a [math]k[/math] such that [math]\mathbb{P}[C_n \geq k] \lt \varepsilon[/math] for [math]n[/math] large enough).

A sequence of Boolean functions [math]f_n[/math] is said to be lame if [math]\mathbb{P}[C_n = 0] \to 1 [/math].

Lameness is a special case of tameness.

Properties

• If a sequence [math]f_n[/math] is tame with respect to [math]p_n[/math], then it is noise stable with respect to [math]p_n[/math].
• If a sequence [math]f_n[/math] is noise sensitive with respect to [math]p_n[/math], then it is volatile with respect to [math]p_n[/math].
• The expected number of sign switches satisfies [math]\mathbb{E}[C] = \sum_i \mathrm{Inf}_i^{p}(f)[/math]. In particular, for [math]p=1/2[/math], the expected number of switches is equal to the unbiased total influence.