# proof of Chernoff-Cramer bound

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

 $\displaystyle\Pr\left\{\sum_{i=1}^{n}\left(X_{i}-E[X_{i}]\right)>\varepsilon\right\}$ $\displaystyle=$ $\displaystyle E\left[h\left(\sum_{i=1}^{n}\left(X_{i}-E[X_{i}]\right)-% \varepsilon\right)\right]\leq$ $\displaystyle\leq$ $\displaystyle E\left[e^{t\left(\sum_{i=1}^{n}\left(X_{i}-E[X_{i}]\right)-% \varepsilon\right)}\right]=$ $\displaystyle=$ $\displaystyle\exp(-\varepsilon t)E\left[e^{\sum_{i=1}^{n}t\left(X_{i}-E[X_{i}]% \right)}\right]=$ $\displaystyle=$ $\displaystyle\exp(-\varepsilon t)E\left[\prod_{i=1}^{n}e^{t\left(X_{i}-E[X_{i}% ]\right)}\right]=$ (by independence) $\displaystyle=$ $\displaystyle\exp(-\varepsilon t)\prod_{i=1}^{n}E\left[e^{t\left(X_{i}-E[X_{i}% ]\right)}\right]=$ $\displaystyle=$ $\displaystyle\exp\left(-\varepsilon t+\sum_{i=1}^{n}\ln E\left[e^{t\left(X_{i}% -E[X_{i}]\right)}\right]\right)=$ $\displaystyle=$ $\displaystyle\exp\left[-\left(t\varepsilon-\psi(t)\right)\right].$

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

 $\Pr\left\{\sum_{i=1}^{n}\left(X_{i}-E[X_{i}]\right)>\varepsilon\right\}\leq e^% {-\sup_{t>0}\left(t\varepsilon-\psi(t)\right)}$

which proves part c).

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

 $\displaystyle E\left[e^{t\left(X_{i}-E[X_{i}]\right)}\right]$ $\displaystyle\geq$ $\displaystyle E[1+t\left(X_{i}-E[X_{i}]\right)]=$ $\displaystyle=$ $\displaystyle E[1]+tE[X_{i}]-tE[E[X_{i}]]=$ $\displaystyle=$ $\displaystyle 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}-EX_{i}\right)}\right]$, so as a conclusion $\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 $t_{1},

 $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

 $\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 $\Psi(x)$ follows from the fact that $\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 $\Psi(x)$ is an increasing function, let’s note that

 $\Psi^{\prime}(0)=\lim_{x\rightarrow 0}\frac{\Psi(x)-\Psi(0)}{x}=\lim_{x% \rightarrow 0}\frac{\Psi(x)}{x}>0$

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

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

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

Title proof of Chernoff-Cramer bound ProofOfChernoffCramerBound 2013-03-22 16:09:05 2013-03-22 16:09:05 Andrea Ambrosio (7332) Andrea Ambrosio (7332) 26 Andrea Ambrosio (7332) Proof msc 60E15