Noise stability

From Boolean Zoo
(Redirected from Stability)
Jump to: navigation, search


For [math]f:\{-1,1\}^{n}\rightarrow\mathbb{\mathbb{R}} [/math] and [math]\rho∈[−1,1][/math], the noise stability of [math]f[/math] at [math]\rho[/math] is [math]Stab_{\rho}[f]=\underset{\underset{\rho-correlated}{(x,y)}}{\mathbb{E}}[f(x)f(y)][/math], where [math] x [/math] and [math]y [/math] are [math]\rho[/math]-correlated if [math] y_{i}=\begin{cases} x_{i} & with\space prabability\space \frac{1}{2}+\frac{1}{2}\rho\\ -x_{i} & with\space prabability\space \frac{1}{2}-\frac{1}{2}\rho \end{cases}[/math]
Informally, the stability tells us what is the chance for the function to stay the same when the input is under noise.


  • In case of [math]f:\{-1,1\}^{n}\rightarrow \{-1,1\}[/math] , [math]Stab_{\rho}[f]=2\underset{\underset{\rho-correlated}{(x,y)}}{\mathbb{P}}[f(x)=f(y)]-1[/math]
  • For [math]f:\{-1,1\}^{n}\rightarrow \{-1,1\}[/math], and for [math]\rho∈[0,1][/math] the connection to Noise sensitivity is by [math]Stab_{\rho}[f]=1-2NS_{\frac{1}{2}-\frac{1}{2}\rho }[f][/math]
  • The Majority function is assumed to be the least stable function among the Linear threshold when [math]n[/math] is big and [math]\rho[/math] is small. [1]


  1. Ryan O'Donnell, Analysis of Boolean functions, Chapter 2.4