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.

  • $\begingroup$ A detailed proof can be found in Ledoux's The Concentration of Measure Phenomenon. Much machinery is needed to prove the result (unfortunately). A proof outline can also be found in Vershynin's High Dimensional Probability but it's along the same lines as the previous one. An elementary proof of a weaker inequality can be found at slide 49 of this pdf. $\endgroup$ – Gabriel Romon May 21 at 8:11
  • $\begingroup$ Thank you sir! @GabrielRomon $\endgroup$ – Jiexiong687691 May 24 at 4:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.