Difference between revisions of "Noise stability"
Or elmackias (talk | contribs) (Created page with " == Definition == f:{− 1 , 1 } n → R and ρ ∈ [ − 1 , 1], the noise stability of f at ρ is Stab ρ [f] = E[f(x)f(y)]. ( x,y ) ρ -correlated") |
m (→Definition) |
||
| (7 intermediate revisions by 2 users not shown) | |||
| Line 1: | Line 1: | ||
== Definition == | == Definition == | ||
| − | + | 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,y ) | + | 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><br> | ||
| + | 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 <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. <ref>Ryan O'Donnell, Analysis of Boolean functions, [http://www.contrib.andrew.cmu.edu/~ryanod/?p=2245 Chapter 2.4]</ref> | ||
| + | |||
| + | == References == | ||
| + | <references/> | ||
Latest revision as of 09:52, 1 November 2020
Definition
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.
Properties
- 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]
References
- ↑ Ryan O'Donnell, Analysis of Boolean functions, Chapter 2.4
