Difference between revisions of "Volatility"
(Created page with "== 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 w...") |
|||
| (3 intermediate revisions by the same user not shown) | |||
| Line 1: | Line 1: | ||
== Definition == | == 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 | + | 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 -1 to 1 with rate <math>p</math>, from 1 to -1 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 -1 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 '''volatile''' if <math>C_n \to \infty</math> in distribution. | ||
| Line 9: | Line 9: | ||
Lameness is a special case of tameness. | Lameness is a special case of tameness. | ||
| − | |||
| − | |||
== Properties == | == Properties == | ||
* If a sequence <math>f_n</math> is tame with respect to <math>p_n</math>, then it is [[noise stability | noise stable]] with respect to <math>p_n</math>. <ref>Johan Jonasson, Jeffrey E. Steif, [https://www.sciencedirect.com/science/article/pii/S0304414916000648 Volatility of Boolean functions], Stochastic Processes and their Applications, Proposition 1.13</ref> | * If a sequence <math>f_n</math> is tame with respect to <math>p_n</math>, then it is [[noise stability | noise stable]] with respect to <math>p_n</math>. <ref>Johan Jonasson, Jeffrey E. Steif, [https://www.sciencedirect.com/science/article/pii/S0304414916000648 Volatility of Boolean functions], Stochastic Processes and their Applications, Proposition 1.13</ref> | ||
| + | * If a sequence <math>f_n</math> is [[noise sensitivity|noise sensitive]] with respect to <math>p_n</math>, then it is volatile with respect to <math>p_n</math>. <ref>Johan Jonasson, Jeffrey E. Steif, [https://www.sciencedirect.com/science/article/pii/S0304414916000648 Volatility of Boolean functions], Stochastic Processes and their Applications, Proposition 1.17</ref> | ||
| + | * 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. <ref>Johan Jonasson, Jeffrey E. Steif, [https://www.sciencedirect.com/science/article/pii/S0304414916000648 Volatility of Boolean functions], Stochastic Processes and their Applications, Proposition 1.19</ref> | ||
| + | |||
== References == | == References == | ||
<references/> | <references/> | ||
Latest revision as of 10:13, 10 November 2021
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 -1 to 1 with rate [math]p[/math], from 1 to -1 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 -1 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]
- 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. [3]
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
- ↑ Johan Jonasson, Jeffrey E. Steif, Volatility of Boolean functions, Stochastic Processes and their Applications, Proposition 1.19
