proof of Chernoff-Cramer bound

Let $h(x)$ be the step function ($h(x)=1$ for $x\ge 0$, $h(x)=0$ for ); then, by generalized Markov inequality, for any $t>0$ and any $\epsilon \ge 0$,

$\mathrm{Pr}\left\{{\displaystyle \sum _{i=1}^n}\left(X_i-E[X_i]\right)>\epsilon \right\}$ $=$ $E\left[h\left({\displaystyle \sum _{i=1}^n}\left(X_i-E[X_i]\right)-\epsilon \right)\right]\le$

$\le$ $E\left[e^{t\left({\sum }_{i=1}^n\left(X_i-E[X_i]\right)-\epsilon \right)}\right]=$

$=$ $\exp (-\epsilon t)E\left[e^{{\sum }_{i=1}^{n}t\left(X_i-E[X_i]\right)}\right]=$

$=$ $\exp (-\epsilon t)E\left[{\displaystyle \prod _{i=1}^n}{e}^{t\left(X_i-E[X_i]\right)}\right]=$

(by independence) $=$ $\exp (-\epsilon t){\displaystyle \prod _{i=1}^n}E\left[e^{t\left(X_i-E[X_i]\right)}\right]=$

$=$ $\exp \left(-\epsilon t+{\displaystyle \sum _{i=1}^n}\ln E\left[e^{t\left(X_i-E[X_i]\right)}\right]\right)=$

$=$ $\exp \left[-\left(t\epsilon -\psi (t)\right)\right].$

Since this expression is valid for any $t>0$, the best bound is obtained taking the supremum:

$$\mathrm{Pr}\left\{\sum _{i=1}^n\left(X_i-E[X_i]\right)>\epsilon \right\}\le e^{-{sup}_{t>0}\left(t\epsilon -\psi (t)\right)}$$

which proves part c).

To prove part a), let’s observe that $\mathrm{\Psi }(0)={sup}_{t>0}(-\psi (t))=-{inf}_{t>0}(\psi (t))$ and that

$E\left[e^{t\left(X_i-E[X_i]\right)}\right]$ $\ge$ $E[1+t\left(X_i-E[X_i]\right)]=$

$=$ $E[1]+tE[X_i]-tE[E[X_i]]=$

$=$ $1=E{\left[e^{t\left(X_i-E[X_i]\right)}\right]}_{t=0}$

that is, $t=0$ is the infimum point for $E\left[e^{t\left(X_i-E[X_i]\right)}\right]$ $\forall i$ and consequently for $\psi (t)={\sum }_{i=1}^n\ln E\left[e^{t\left(X_i-E{X}_i\right)}\right]$, so as a conclusion $\mathrm{\Psi }(0)=-\psi (0)=0$

b) Let $x>0$ be fixed and let $t_0$ be the supremum point for $tx-\psi (t)$; we have to show that $t_{0}x-\psi (t_0)>0$.

By differentiation, ${\psi }^{\prime }(t_0)=x$.

Let’s recall that the moment generating function is convex, so ${\psi }^{\prime \prime }(t)>0$. Writing the Taylor expansion for $\psi (t)$ around $t=t_0$, we have, with a suitable ,

$$0=\psi (0)=\psi (t_0)-{\psi }^{\prime }(t_0)t_0+\frac{1}{2}{\psi }^{\prime \prime }(t_1)t_0^2$$

that is

$$\mathrm{\Psi }(x)=t_{0}x-\psi (t_0)=t_0{\psi }^{\prime }(t_0)-\psi (t_0)=\frac{1}{2}{\psi }^{\prime \prime }(t_1)t_0^2>0$$

The convexity of $\mathrm{\Psi }(x)$ follows from the fact that $\mathrm{\Psi }(x)$ is the supremum of the linear (and hence convex) functions $tx-\psi (t)$ and so must be convex itself.

Eventually, in to prove that $\mathrm{\Psi }(x)$ is an increasing function, let’s note that

$${\mathrm{\Psi }}^{\prime }(0)=\underset{x\to 0}{lim}\frac{\mathrm{\Psi }(x)-\mathrm{\Psi }(0)}{x}=\underset{x\to 0}{lim}\frac{\mathrm{\Psi }(x)}{x}>0$$

and that, by Taylor formula with Lagrange form remainder, for a $\xi =\xi (x)$

$${\mathrm{\Psi }}^{\prime }(x)={\mathrm{\Psi }}^{\prime }(0)+{\mathrm{\Psi }}^{\prime \prime }(\xi )x\ge 0$$

since ${\mathrm{\Psi }}^{\prime \prime }(\xi )\ge 0$ by convexity and $x\ge 0$ by hypotheses.

Title	proof of Chernoff-Cramer bound
Canonical name	ProofOfChernoffCramerBound
Date of creation	2013-03-22 16:09:05
Last modified on	2013-03-22 16:09:05
Owner	Andrea Ambrosio (7332)
Last modified by	Andrea Ambrosio (7332)
Numerical id	26
Author	Andrea Ambrosio (7332)
Entry type	Proof
Classification	msc 60E15