proof of Chernoff-Cramer bound

Let h(x) be the step functionPlanetmathPlanetmath (h(x)=1 for x0, h(x)=0 for x<0); then, by generalized Markov inequalityMathworldPlanetmath, for any t>0 and any ε0,

Pr{i=1n(Xi-E[Xi])>ε} = E[h(i=1n(Xi-E[Xi])-ε)]
= exp(-εt)E[ei=1nt(Xi-E[Xi])]=
= exp(-εt)E[i=1net(Xi-E[Xi])]=
(by independence) = exp(-εt)i=1nE[et(Xi-E[Xi])]=
= exp(-εt+i=1nlnE[et(Xi-E[Xi])])=
= exp[-(tε-ψ(t))].

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


which proves part c).

To prove part a), let’s observe that Ψ(0)=supt>0(-ψ(t))=-inft>0(ψ(t)) and that

E[et(Xi-E[Xi])] E[1+t(Xi-E[Xi])]=
= E[1]+tE[Xi]-tE[E[Xi]]=
= 1=E[et(Xi-E[Xi])]t=0

that is, t=0 is the infimum point for E[et(Xi-E[Xi])] i and consequently for ψ(t)=i=1nlnE[et(Xi-EXi)], so as a conclusion Ψ(0)=-ψ(0)=0

b) Let x>0 be fixed and let t0 be the supremum point for tx-ψ(t); we have to show that t0x-ψ(t0)>0.

By differentiationMathworldPlanetmath, ψ(t0)=x.

Let’s recall that the moment generating function is convex, so ψ′′(t)>0. Writing the Taylor expansionMathworldPlanetmath for ψ(t) around t=t0, we have, with a suitable t1<t0,


that is


The convexity of Ψ(x) follows from the fact that Ψ(x) is the supremum of the linear (and hence convex) functions tx-ψ(t) and so must be convex itself.

Eventually, in to prove that Ψ(x) is an increasing function, let’s note that


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


since Ψ′′(ξ)0 by convexity and x0 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