Noise sensitivity

TODO: fix definition of "noise sensitive with respect to...". It doesn't really match what's written in "Volatility of Boolean functions" (the entry on volatility needs those definitions)

Definition

For [math]f:\{-1,1\}^{n}\longrightarrow\{-1,1\}[/math] and [math]\delta\in[0,1][/math], the noise sensitivity of [math]f[/math] at [math]\delta[/math], [math]\mathbf{NS}_{\delta}[f][/math], is the probability that [math]f(x)\neq f(y)[/math] when [math]x\sim\{-1,1\}^{n}[/math] is uniformly random and [math]y[/math] is formed from [math]x[/math] by reversing each bit independently with probability [math]\delta[/math].

A series of functions [math]f_n:\{-1,1\}^n \to \{-1,1\}[/math] is said to be noise sensitive with respect to the sequence [math]\delta_n \gt 0[/math], we have that [math]\mathbb{E}[f_n(x)f_n(y)] - \mathbb{E}[f_n]^2 \to 0[/math] as [math]n \to \infty [/math]. If [math]\delta[/math] is held fixed, we just say that the sequence is noise sensitive.

Properties

• The connection between noise sensitivity and stability is given by [math]\mathbf{NS}_{\delta}[f]=\frac{1}{2}-\frac{1}{2}Stab_{1-2\delta}[f][/math].
• For [math]\delta\leq\frac{1}{2}[/math], and [math]f[/math] is linear threshold function ([math]f(x)=sgn(\sum_{i=1}^{n}\omega_{i}x_{i}-t)[/math]), then [math]\mathbf{NS}_{\delta}[f]\leq2\delta^{1/2}[/math]. furthermore, [math]\underset{\delta\rightarrow0}{\limsup}\frac{\limsup_{n\rightarrow\infty}\sup_{\omega,t}\mathbf{NS}_{\delta}[f]}{\sqrt{\delta}}\leq\sqrt{\frac{2}{\pi}}[/math].
• The noise sensitivity can be lower-bounded by the total influence of a function: [math]\mathbf{NS}_{1/n}(f) \geq \mathrm{Inf}(f)/ne[/math].