Concentration in Gauss space

191 Views Asked by At

This is a theorem called Concentration in Gauss space. Let $f$ be a real valued Lipschitz function on $\mathbb {R}^{n}$ with Lipschitz constant $K$, i.e. $\left|f(x)-f(y)\right|\leq K\|x-y\|_{2}$ for all $x,y\in \mathbb {R}^{n}$ (such functions are also called K-Lipschitz). Let $X$ be the standard normal random vector in $\mathbb {R}^{n}$. Then for every $t\geq 0$ one has \begin{align*} \mathbb {P}\left\{f(X)-\mathbb {E}f(X)>t\right\}\leq \text{exp}(-t^{2}/2K^{2}). \end{align*} We have \begin{align*} \mathbb {P}\left\{f(X)-\mathbb {E}f(X)>t\right\}=\mathbb {P}\left\{e^{\lambda(f(x)-\mathbb {E}f(x))}>e^{\lambda t}\right\}\leq \mathbb {E}e^{\lambda(f(x)-\mathbb {E}f(x))}/e^{\lambda t} \end{align*} I wonder how to continue from here. Or maybe just inform me where to find the proof. Thanks a lot.