The Chernoff-Cramèr inequality is a very general and powerful way of bounding random variables. Compared with the famous Chebyshev bound, which implies inverse polynomial 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)
Namely, one has:
that is, is the Legendre of the cumulant generating function of the 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 (http://planetmath.org/BernsteinInequality), Kolmogorov, Prohorov (http://planetmath.org/ProhorovInequality), Bennett (http://planetmath.org/BennettInequality),
Hoeffding and Chernoff ones are worth mentioning. All of these
inequalities are obtained imposing various further conditions on random variables, which turn out to affect the general form of the cumulant generating function .
2) Sometimes, instead of bounding the sum of n independent random variables, one needs to estimate they ” i.e. the quantity ; 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 .
3) It turns out that the Chernoff-Cramer bound is asymptotically sharp, as CramÃÂ¨r theorem shows.
|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)|
|Author||Andrea Ambrosio (7332)|