PlanetMath (more info)
 Math for the people, by the people. Sponsor PlanetMath
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
Owner confidence rating: High Entry average rating: No information on entry rating
Chernoff-Cramer bound (Theorem)

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' behaviour.

Theorem: (Chernoff-Cramèr inequality)

Let $\{X_{i}\}_{i=1}^{n}$ be a collection of independent random variables such that $E[\exp \left( tX_{i}\right) ]<+\infty $ $\forall i$ in a right neighborhood of $t=0$ , i.e. for any $t\in(0,c)$ (Cramèr condition).

Then a zero-valued for $x=0$ , positive, strictly increasing, strictly convex function $\Psi (x):[0,\infty )\mapsto R^{+}$ exists such that:
$$ \Pr\left\{ \sum_{i=1}^{n}\left( X_{i}-E[X_{i}]\right) >\varepsilon \right\} \leq \exp \left( -\Psi (\varepsilon )\right) \ \forall \varepsilon \geq 0 $$

Namely, one has: \begin{eqnarray*} \Psi (x) &=&\sup_{0 < t < c}\left( tx -\psi (t)\right) \\ \psi (t) &=&\sum_{i=1}^{n}\ln E\left[ e^{t\left( X_{i}-EX_{i}\right) }\right] =\sum_{i=1}^{n}\left(\ln E\left[ e^{tX_{i}}\right] -tE\left[ X_{i}\right]\right) \end{eqnarray*} that is, $\Psi (x)$ is the Legendre transform of the cumulant generating function of the $\sum_{i=1}^{n}\left( X_{i}-E[X_{i}]\right)$ random variable.

Remarks:

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 $X_{i}$ random variables, which turn out to affect the general form of the cumulant generating function $\psi(t)$ .
2) Sometimes, instead of bounding the sum of n independent random variables, one needs to estimate they 'mean' i.e. the quantity $\frac{1}{n}\sum_{i=1}^{n}X_i$ ; in order to reuse Chernoff-Cramér bound, it's enough to note that $$ \Pr\left\{\frac{1}{n}\sum_{i=1}^{n}\left( X_{i}-E[X_{i}]\right) >\varepsilon^{\prime}\right\}=\Pr\left\{\sum_{i=1}^{n}\left( X_{i}-E[X_{i}]\right) >n\varepsilon^{\prime}\right\} $$ so that one has only to replace, in the above stated inequality, $\varepsilon$ with $n\varepsilon^{\prime}$ .
3) It turns out that the Chernoff-Cramer bound is asymptotically sharp, as Cramèr limit theorem shows.




"Chernoff-Cramer bound" is owned by Andrea Ambrosio.
(view preamble | get metadata)

View style:

See Also: Hoeffding inequality for bounded independent random variables


Attachments:
proof of Chernoff-Cramer bound (Proof) by Andrea Ambrosio
Log in to rate this entry.
(view current ratings)

Cross-references: estimate, sum, point, cumulant generating function, strictly convex function, strictly increasing, positive, neighborhood, right, independent, collection, theorem, exponential, polynomial, inverse, implies, bound, random variables, inequality
There are 3 references to this entry.

This is version 43 of Chernoff-Cramer bound, born on 2006-08-08, modified 2006-09-20.
Object id is 8230, canonical name is ChernoffCramerBound.
Accessed 3064 times total.

Classification:
AMS MSC60E15 (Probability theory and stochastic processes :: Distribution theory :: Inequalities; stochastic orderings)

Pending Errata and Addenda
None.
[ View all 5 ]
Discussion
Style: Expand: Order:
forum policy

No messages.

Interact
post | correct | update request | prove | add result | add corollary | add example | add (any)