Chernoff-Cramer bound

The Chernoff-Cramèr inequalityMathworldPlanetmath is a very general and powerful way of bounding random variablesMathworldPlanetmath. Compared with the famous Chebyshev bound, which implies inverseMathworldPlanetmathPlanetmathPlanetmathPlanetmath polynomialPlanetmathPlanetmath decay inequalities, the Chernoff-Cramèr method yields exponential decay inequalities, at the cost of needing a few more hypotheses on random variables’ .

Theorem: (Chernoff-Cramèr inequality)

Let {Xi}i=1n be a collection of independentPlanetmathPlanetmath random variables such that E[exp(tXi)]<+  i in a right neighborhoodMathworldPlanetmath of t=0, i.e. for any t(0,c) (Cramèr condition).

Then a zero-valued for x=0, positive, strictly increasing, strictly convex function Ψ(x):[0,)R+ exists such that:


Namely, one has:

Ψ(x) = sup0<t<c(tx-ψ(t))
ψ(t) = i=1nlnE[et(Xi-EXi)]=i=1n(lnE[etXi]-tE[Xi])

that is, Ψ(x) is the Legendre of the cumulant generating function of the i=1n(Xi-E[Xi]) random variable.


1) Besides its importance for theoretical questions, the Chernoff-Cramér bound is also the starting point to derive many deviation or concentration inequalities, among which Bernstein (, Kolmogorov, Prohorov (, Bennett (, Hoeffding and Chernoff ones are worth mentioning. All of these inequalities are obtained imposing various further conditions on Xi random variables, which turn out to affect the general form of the cumulant generating function ψ(t).
2) Sometimes, instead of bounding the sum of n independent random variables, one needs to estimate they ” i.e. the quantity 1ni=1nXi; in to reuse Chernoff-Cramér bound, it’s enough to note that


so that one has only to replace, in the above stated inequality, ε with nε.
3) It turns out that the Chernoff-Cramer bound is asymptotically sharp, as Cramèr theorem shows.

Title Chernoff-Cramer bound
Canonical name ChernoffCramerBound
Date of creation 2013-03-22 16:09:02
Last modified on 2013-03-22 16:09:02
Owner Andrea Ambrosio (7332)
Last modified by Andrea Ambrosio (7332)
Numerical id 46
Author Andrea Ambrosio (7332)
Entry type Theorem
Classification msc 60E15
Related topic HoeffdingInequalityForBoundedIndependentRandomVariables