# Noise sensitivity

## Definition

### Uniform case

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

 $\mathbf{NS}_{\delta}[f] = \mathbb{P}[f(x)\neq f(y)]$

A series of functions $f_n:\{-1,1\}^n \to \{-1,1\}$ is said to be noise sensitive if for every $\delta \gt 0$, we have $\mathbb{E}[f_n(x)f_n(y)] - \mathbb{E}[f_n]^2 \to 0$ as $n \to \infty$.

### $p$-biased case

A similar concept can be defined for a $p$-biased measure, i.e when the random vector $x$ has iid entries which are 1 with probability $p$ and 0 with probability $1-p$. In this case, the random vector $y$ is defined so that the bit 1 is reversed with probability $2\delta p$ and the bit 0 is reversed with probability $2\delta (1-p)$. (the definition only makes sense for $\delta$ which doesn't make the probability larger than 1).

A series of functions $f_n:\{-1,1\}^n \to \{-1,1\}$ is then said to be noise sensitive with respect to $p_n$ if for every $\delta \gt 0$, we have $\mathbb{E}[f_n(x)f_n(y)] - \mathbb{E}[f_n]^2 \to 0$ as $n \to \infty$.

## Properties

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

## References

1. Ryan O'Donnell, Analysis of Boolean functions, Chapter 2.4 [1]
2. Peres (2004). "Noise Stability of Weighted Majority" [2]
3. Prahladh Harsha, Adam Klivans, Raghu Meka, Bounding the Sensitivity of Polynomial Threshold Functions, Lemma 8.1