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