# Noise sensitivity

## Definition

For $f:\{-1,1\}^{n}\longrightarrow\{-1,1\}$ and $\delta\in[0,1]$, the noise sensitivity of $f$ at $\delta$, $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$.

## Properties

• The connection between noise sensitivity and Stability is given by $NS_{\delta}[f]=\frac{1}{2}-\frac{1}{2}Stab_{1-2\delta}[f]$
• 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 $NS_{\delta}[f]\leq2\delta^{1/2}$. furthermore, $\underset{\delta\rightarrow0}{\limsup}\frac{\limsup_{n\rightarrow\infty}\sup_{\omega,t}NS_{\delta}[f]}{\sqrt{\delta}}\leq\sqrt{\frac{2}{\pi}}$ (Peres, 2006)

## References

[2]

1. Ryan O'Donnell, Analysis of Boolean functions, Chapter 2.4 [1]
2. Peres (2004). "Noise Stability of Weighted Majority" [2]