0.7 Chernoff's bound and hoeffding's inequality  (Page 2/2)

Take

So, the probability goes to zero at a rate of at least $n^{-1}$ . However, it turns out that this is an extremely loose bound. Accordingto the Central Limit Theorem

in distribution. This suggests that for large values of n,

That is, the Gaussian tail probability is tending to zero exponentially fast.

Chernoff's bound

Note that for any nonnegative random variable $Z$ and $t>0$ ,

Chernoff's bound is based on finding the value of $s$ that minimizes the upper bound. If $Z$ is a sum of independent random variables. For example, say

then the bound becomes

Thus, the problem of finding a tight bound boils down to finding a good bound for $E\left[s^{s(L_i-E\left[L_i\right])}\right]$ . Chernoff ('52), first studied this situation for binary random variables. Then,Hoeffding ('63) derived a more general result for arbitrary bounded random variables.

Hoeffding's indequality

Hoeffding's inequality

Let $Z_1,Z_2,...,Zn$ be independent bounded random variables such that $Z_i\in [a_i,b_i]$ with probability 1. Let $S_n={\sum }_{i=1}^n{Z}_i$ . Then for any $t>0$ , we have

The key to proving Hoeffding's inequality is the following upper bound: if $Z$ is a random variable with $E\left[Z\right]=0$ and $a\le Z\le b,$ then

This upper bound is derived as follows. By the convexity of theexponential function,

Thus,

Now let

Then we have

To minimize the upper bound let's express $\phi \left(u\right)$ in a Taylor's series with remainder :

Now, ${\phi }^{\text{'}\text{'}}\left(u\right)$ is maximized by

So,

Now, we can apply this upper bound to derive Hoeffding's inequality.

Similarly, $P(E\left[S_n\right]-S_n\ge t)\le e^{\frac{-2t^2}{{\sum }_{i=1}^n{(b_i-a_i)}^2}}$ . This completes the proof of the Hoeffding's theorem.