Theorem 1: Gaussian Tail Inequality
Given \({{x}_{1}},\cdots ,{{x}_{n}}\sim N\left( 0,1 \right)\) then, \(P\left( \left| X \right|>\varepsilon \right)\le \frac{2{{e}^{-{{{\varepsilon }^{2}}}/{2}\;}}}{\varepsilon }\) and \(P\left( \left| {{{\bar{X}}}_{n}} \right|>\varepsilon \right)\le \frac{2}{\sqrt{n}\varepsilon }{{e}^{-{n{{\varepsilon }^{2}}}/{2}\;}}\overset{l\arg e\ n}{\mathop{\le }}\,{{e}^{-{n{{\varepsilon }^{2}}}/{2}\;}}\).
Proof of Gaussian Tail Inequality
Consider a univariate \({{x}_{1}},\cdots ,{{x}_{n}}\sim N\left( 0,1 \right)\), then the probability density function is given as \(\phi \left( x \right)=\frac{1}{\sqrt{2\pi }}{{e}^{-\frac{{{x}^{2}}}{2}}}\).
Let’s take the derivative w.r.t \(x\) we get:
\[\frac{d\phi \left( x \right)}{dx}={\phi }'\left( x \right)=\frac{d\left( \frac{1}{\sqrt{2\pi }}{{e}^{-\frac{{{x}^{2}}}{2}}} \right)}{dx}=\frac{1}{\sqrt{2\pi }}\frac{d\left( \,{{e}^{-\frac{{{x}^{2}}}{2}}} \right)}{dx}=\frac{1}{\sqrt{2\pi }}\frac{d\left( \,{{e}^{-\frac{{{x}^{2}}}{2}}} \right)}{d\left( -\frac{{{x}^{2}}}{2} \right)}\frac{d\left( -\frac{{{x}^{2}}}{2} \right)}{dx}=\frac{1}{\sqrt{2\pi }}{{e}^{-\frac{{{x}^{2}}}{2}}}\left( -x \right)=-x\phi \left( x \right)\]
Let’s define the gaussian tail inequality.