# Noise stability

(Redirected from Stability)

## Definition

For $f:\{-1,1\}^{n}\rightarrow\mathbb{\mathbb{R}}$ and $\rho∈[−1,1]$, the noise stability of $f$ at $\rho$ is $Stab_{\rho}[f]=\underset{\underset{\rho-correlated}{(x,y)}}{\mathbb{E}}[f(x)f(y)]$, where $x$ and $y$ are $\rho$-correlated if $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}$
Informally, the stability tells us what is the chance for the function to stay the same when the input is under noise.

## Properties

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

## References

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