Chernoff Bounds

01 Mar 2018

Prologue To The Chernoff Bounds

The Chernoff bounds is essential another variation based on the Markov inequality, it derivates the exponential deviation bounds.

Chernoff Bounds

Let $Z$ be any random variable, then for any $t>0$,
$\;\;P(Z\ge E\lbrack Z\rbrack+t)\le\underset{\lambda\ge 0}{min}E\lbrack e^{\lambda\cdot (Z-E\lbrack Z\rbrack)}\rbrack\cdot e^{-\lambda\cdot t}$=$\underset{\lambda\ge 0}{min}M_{Z-E\lbrack Z\rbrack}(\lambda)\cdot e^{-\lambda\cdot t}$
and
$\;\;P(Z\le E\lbrack Z\rbrack-t)\le\underset{\lambda\ge 0}{min}E\lbrack e^{\lambda\cdot (E\lbrack Z\rbrack-Z)}\rbrack\cdot e^{-\lambda\cdot t}$=$\underset{\lambda\ge 0}{min}M_{E\lbrack Z\rbrack-Z}(\lambda)\cdot e^{-\lambda\cdot t}$
; where $M_{Z}(\lambda)$=$E\lbrack exp(\lambda\cdot Z)\rbrack$ is the moment generating function of $Z$.

Proof:
➀for any $\lambda>0$, we have:
$Z\ge E\lbrack Z\rbrack+t$
$\Leftrightarrow e^{\lambda\cdot Z}\ge e^{\lambda\cdot (E\lbrack Z\rbrack+t)}$
Or equivalently,
$Z-E\lbrack Z\rbrack\ge t$
$\Leftrightarrow e^{\lambda\cdot (Z-E\lbrack Z\rbrack)}\ge e^{\lambda\cdot t}$
➁by Markov inequality, below holds:
$P(\left|Z-E\lbrack Z\rbrack\right|\ge t)$
$=P(e^{\lambda\cdot (Z-E\lbrack Z\rbrack)}\ge e^{\lambda\cdot t})\le E\lbrack e^{\lambda\cdot (Z-E\lbrack Z\rbrack)}\rbrack\cdot e^{-\lambda\cdot t}$
➂the second inequality could be proved in the similar way.

To be believed that a reasonable upper bound could be built by choosing appropriate $\lambda$.

Chernoff Bounds Extension

We can further extend Chernoff bounds with summation of multiple random varaibles.
➀suppose that all $Z_i$’s are independent and zero meanfor all $i$, then we have it that:
$\;\;M_{Z_1+…+Z_n}=\prod_{i=1}^{n}M_{Z_i}(\lambda)$
, which is a consequence of the moment generating function, because the independence of each $Z_{i}$.
$E\lbrack exp(\lambda\cdot\sum_{i=1}^{n}Z_{i})\rbrack$
=$E\lbrack \prod_{i=1}^{n}exp(\lambda\cdot Z_{i})\rbrack$
=$\prod_{i=1}^{n}E\lbrack exp(\lambda\cdot Z_{i})\rbrack$
➁by Chernoff inequality, for any $\lambda>0$,
$P(\sum_{i=1}^{n}Z_{i}\ge t)\le \prod_{i=1}^{n}E\lbrack exp(\lambda\cdot Z_{i})\rbrack\cdot e^{-\lambda\cdot t}$
$\Leftrightarrow P(\sum_{i=1}^{n}Z_{i}\ge t)\le (E\lbrack exp(\lambda\cdot Z_{1})\rbrack)^{n}\cdot e^{-\lambda\cdot t}$