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]. [1]
- 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]. [2]
References
- ↑ Johan Jonasson, Jeffrey E. Steif, Volatility of Boolean functions, Stochastic Processes and their Applications, Proposition 1.13
- ↑ Johan Jonasson, Jeffrey E. Steif, Volatility of Boolean functions, Stochastic Processes and their Applications, Proposition 1.17
