Chernoff Bounds For Normal Distribution

01 Mar 2018

Prologue To The Chernoff Bounds For Normal Distribution

The Chernoff bounds is a convenient way to build the shaper bounds in exponential form for normal distributions.

Chernoff Bounds For Normal Distribution

Given that $Z$ is a random variable, normally distributed in $Z\sim N(0,\sigma^2)$, then
$\;\;P(Z\ge t)\le e^{(\lambda\cdot\sigma)^{2}}\cdot e^{-\lambda\cdot t}$
, where $M_{Z}(\lambda)$=$e^{(\lambda\cdot\sigma)^{2}}$

proof::mjtsai1974

The proof would be categorized into 4 major parts, the first part is to ask for $E\lbrack e^{\lambda\cdot Z}\rbrack$, the second part is to figure out the r-th moment, we’ll make reference to the ratio test theorem in the third part, finally is the upper bounds in the Chernoff Bounds form.
[1]We begin from $E\lbrack e^{\lambda\cdot Z}\rbrack$
First, express the MGF of Z in terms of the Taylor series:
$M_{Z}(\lambda)$
=$E\lbrack e^{\lambda\cdot Z}\rbrack$
=$E\lbrack 1+\frac {\lambda\cdot Z}{1!}+\frac {(\lambda\cdot Z)^{2}}{2!}+\frac {(\lambda\cdot Z)^{3}}{3!}+…\rbrack$
=$1$+$\frac {\lambda}{1!}\cdot E\lbrack Z\rbrack$+$\frac {(\lambda)^{2}}{2!}\cdot E\lbrack Z^{2}\rbrack$+$\frac {(\lambda)^{3}}{3!}\cdot E\lbrack Z^{3}\rbrack$+$\frac {(\lambda)^{4}}{4!}\cdot E\lbrack Z^{4}\rbrack$+…
[2]Next to ask for the r-th ordinary moment of each term.
➀$E\lbrack Z^{r}\rbrack$=$\int_{0}^{\infty}\frac {z^{r}}{\sqrt {2\cdot\pi}}\cdot e^{-\frac {z^{2}}{2\cdot\sigma^{2}}}\operatorname dz$
; where $z\in Z$, $z$ is the events.
➁take $x$=$\frac {z^{2}}{2\cdot\sigma^{2}}$, then
$z$=$\sqrt{2\cdot\sigma^{2}\cdot x}$, and
$\operatorname dz$=$\frac {\sigma^{2}}{z}\cdot\operatorname dx$
➂just replace $\operatorname dz$ with $\operatorname dx$
$E\lbrack Z^{r}\rbrack$
=$\frac {1}{\sqrt {2\cdot\pi}}\int_{0}^{\infty}z^{r}\cdot e^{-x}\cdot\frac {\sigma^{2}}{z}\cdot\operatorname dx$
=$\frac {\sigma^{2}}{\sqrt {2\cdot\pi}}\int_{0}^{\infty}z^{r-1}\cdot e^{-x}\operatorname dx$
=$\frac {\sigma^{2}}{\sqrt {2\cdot\pi}}\cdot\Gamma(r)$
, where $\Gamma(r)$=$\int_{0}^{\infty}z^{r-1}\cdot e^{-x}\operatorname dx$, it is just the Gamma function in $Z$.
[3]We know $\Gamma(n)$=$(n-1)!$ in Introduction To The Gamma Distribution, then,
$M_{Z}(\lambda)$
=$1$+$\frac {\lambda}{1!}\cdot E\lbrack Z\rbrack$+$\frac {(\lambda)^{2}}{2!}\cdot E\lbrack Z^{2}\rbrack$+$\frac {(\lambda)^{3}}{3!}\cdot E\lbrack Z^{3}\rbrack$+$\frac {(\lambda)^{4}}{4!}\cdot E\lbrack Z^{4}\rbrack$+…
=$1$+$\frac {\lambda}{1!}\cdot\frac {\sigma^{2}}{\sqrt {2\cdot\pi}}\cdot\Gamma(1)$+$\frac {(\lambda)^{2}}{2!}\cdot\frac {\sigma^{2}}{\sqrt {2\cdot\pi}}\cdot\Gamma(2)$+$\frac {(\lambda)^{3}}{3!}\cdot\frac {\sigma^{2}}{\sqrt {2\cdot\pi}}\cdot\Gamma(3)$+$\frac {(\lambda)^{4}}{4!}\cdot\frac {\sigma^{2}}{\sqrt {2\cdot\pi}}\cdot\Gamma(4)$+…
=$1$+$0$+$\frac {(\lambda)^{2}}{2!}\cdot\frac {\sigma^{2}}{\sqrt {2\cdot\pi}}\cdot 1!$+$\frac {(\lambda)^{3}}{3!}\cdot\frac {\sigma^{2}}{\sqrt {2\cdot\pi}}\cdot 2!$+$\frac {(\lambda)^{4}}{4!}\cdot\frac {\sigma^{2}}{\sqrt {2\cdot\pi}}\cdot 3!$+…
…$\Gamma(1)$=$(1-1)!$=$0$
=$1$+$\frac {(\lambda)^{2}}{2}\cdot\frac {\sigma^{2}}{\sqrt {2\cdot\pi}}$+$\frac {(\lambda)^{3}}{3}\cdot\frac {\sigma^{2}}{\sqrt {2\cdot\pi}}$+$\frac {(\lambda)^{4}}{4}\cdot\frac {\sigma^{2}}{\sqrt {2\cdot\pi}}$+$\frac {(\lambda)^{5}}{5}\cdot\frac {\sigma^{2}}{\sqrt {2\cdot\pi}}$…
=$1$+$(\lambda\cdot \sigma)^{2}\cdot(\frac {1}{2\cdot\sqrt{2\cdot\pi}}$+$\frac {\lambda}{3\cdot\sqrt{2\cdot\pi}}$+$\frac {\lambda^{2}}{4\cdot\sqrt{2\cdot\pi}}$+$\frac {\lambda^{3}}{5\cdot\sqrt{2\cdot\pi}}$+…+$)$

Be recalled that we have convergence evaluation by the ratio test theorem in Series Convergence.

If $\frac {a_{n+1}}{a_n}$ approaches a limit $L<1$, the series converges.

➀$\frac {a_2}{a_1}$=$\frac {\lambda^{3}/3}{\lambda^{2}/2}$=$\frac {2}{3}\cdot\lambda$
➁$\frac {a_3}{a_2}$=$\frac {\lambda^{4}/4}{\lambda^{3}/3}$=$\frac {3}{4}\cdot\lambda$
➂$\frac {a_4}{a_3}$=$\frac {\lambda^{5}/5}{\lambda^{4}/4}$=$\frac {4}{5}\cdot\lambda$
Trivially, $\frac {a_2}{a_1}$<$\frac {a_3}{a_2}$<$\frac {a_4}{a_3}$<…$\rightarrow 1$, the ratio is increasing and becomes much much close to $1$, this series would just diverge to infinity, by ratio test theorem.
Therefore, the whole equality becomes
$M_{Z}(\lambda)$
=$1$+$(\lambda\cdot\sigma)^{2}\cdot(\frac {1}{2\cdot\sqrt{2\cdot\pi}}$+$\frac {\lambda}{3\cdot\sqrt{2\cdot\pi}}$+$\frac {\lambda^{2}}{4\cdot\sqrt{2\cdot\pi}}$+$\frac {\lambda^{3}}{5\cdot\sqrt{2\cdot\pi}}$+…+$)$
$\approx 1+(\lambda\cdot\sigma)^{2}\cdot\infty$
$\approx\lim_{h\rightarrow 0}1+\frac {(\lambda\cdot\sigma)^{2}}{h}$
$\approx\lim_{h\rightarrow\infty}(1+\frac {(\lambda\cdot\sigma)^{2}}{h})^{h}$
=$e^{(\lambda\cdot\sigma)^{2}}$
[4]By Chernoff Bounds, for any $\lambda>0$, then
$P(Z\ge t)\le \frac {E\lbrack e^{(\lambda\cdot Z)}\rbrack}{e^{\lambda\cdot t}}$
$\Rightarrow P(Z\ge t)\le e^{(\lambda\cdot\sigma)^{2}}\cdot e^{-\lambda\cdot t}$