# Chernoff inequalities

Chernoff inequalities are inequalities that express concentration around the expectation of a random variable $X=\sum_iX_i$ where the $X_i$ are i.i.d random variables

I have been encountering these inequalities at differenet contexts and for several distributions of the $X_i's$. Nevertheless whenever I try to understand the proof for it, it seems to me that the proof is just a sequence of tricks and I fail to get any insight.

1. Do you know of any insightful, perhaps using "higher math", way to view these inequalities?

2. For which distributions of the $X_i's$ can one expect to get a chernoff bound for $\sum_iX_i$?

-
The proof uses a very important trick: considering the moment-generating function. This trick is very useful to know, for example it is used in some proofs of the various limit theorems, and in statistical physics the moment generating function is an important quantity called the partition function. – Colin McQuillan Jun 22 '12 at 9:27
Have you read Terence Tao's notes on concentration of measure? I think he says some insightful things about Chernoff bounds there (but I can't access it at the moment). – Qiaochu Yuan Jun 22 '12 at 11:29

These proofs are definitely not a sequence of tricks. Rather, one applies again and again a quite important principle, which can be stated as:

Find a good pointwise inequality between random variables and integrate it.

For example, Markov inequality is the integrated version of the pointwise inequality $$t\,\mathbf 1_A\leqslant X,\quad\text{with}\quad A=[X\geqslant t],$$ which holds for every positive $t$ and random variable $X$ such that $X\geqslant0$ almost surely.

Likewise, Bienaymé-Chebyshev inequality is the integrated version of the pointwise inequality $$t^2\,\mathbf 1_A\leqslant|X-\mathrm E(X)|^2,\quad\text{with}\quad A=[|X-\mathrm E(X)|\geqslant t],$$ which holds for every positive $t$ and with no restriction on the sign of $X$.

Another example is Chernoff bound, which is the integrated version of the inequality $$\mathrm e^{xt}\,\mathbf 1_A\leqslant\mathrm e^{xS},\quad\text{with}\quad A=[S\geqslant t],$$ which is valid for every random variable $S$ and every real number $t$ but only for $x\geqslant0$.

The following steps are to choose cleverly $t$ and $x$, and to be able to estimate $\mathrm E(\mathrm e^{xS})$. For example, when $S=X_1+\cdots+X_n$ is a sum of i.i.d. random variables $X_k$ distributed like $X$, one knows that $\mathrm E(\mathrm e^{xS})=\left(\mathrm E(\mathrm e^{xX})\right)^n$ hence $$\mathrm P(S\geqslant nt)\leqslant\mathrm e^{-nxt}\left(\mathrm E(\mathrm e^{xX})\right)^n=\mathrm e^{-n\Lambda(x,t)},$$ with $$\Lambda(x,t)=xt-\log\mathrm E(\mathrm e^{xX}),$$ and the crucial question now is to determine if there exists some $x\geqslant0$ such that $\Lambda(x,t)\gt0$. This can only happen for $x\gt0$ since $\Lambda(0,t)=0$ hence Chernoff bounds are only relevant when $\mathrm E(\mathrm e^{xX})$ is finite for (at least) some (small) $x\gt0$.

-

1) I wouldn't consider this as a quantitative version of the central limit theorem, but rather as a quantitative version of large deviation theorems (the two are related, of course). Let us focus on the result, and not on the methods you use to get them. Let $(X_i)$ be a sequence of i.i.d., $\mathbb{R}$-valued, centered, bounded random variables. I'll denote by $(S_n)$ the sequence of its partial sums. A large deviation principle tells you that there exists a rate function $I: \mathbb{R} \to \mathbb{R}_+$ such that, for any open set $O$:

$$- \inf_O I \leq \liminf_{n \to + \infty} \frac{\ln \mathbb{P} (S_n/n \in O)}{n},$$

and for any closed set $F$:

$$\liminf_{n \to + \infty} \frac{\ln \mathbb{P} (S_n/n \in F)}{n} \leq - \inf_F I.$$

In other words, the probability that the sum $S_n$ is large (say, $S_n \geq \varepsilon n$ for a fixed $\varepsilon$) decreases exponentially in $n$, roughly at speed $e^{- I (\varepsilon)n}$.

A notable feature of these large deviation principles for i.i.d. random variable is that the function $I$, which governs the speed of the decay, is the Lapaplace-legendre transform of the characteristic function of $X$. In other words, exactly what you get with the Chernoff bounds! So the Chernoff bounds you give you a quantitative, upper bound for the large deviation principles:

$$\mathbb{P} (S_n/n \geq \varepsilon) \leq e^{- I(\varepsilon) n},$$

or equivalently,

$$\frac{\mathbb{P} (S_n/n \geq \varepsilon)}{n} \leq - I(\varepsilon).$$

In a more general setting, the rate function $I$ is related to the entropy of some system (you get a large entropy [that is, small for a physicist - there is often a sign change] when the sum $S_n$ is far from its typical state).

==========

There a point which is worthy of note, but has not been raised yet. You can show that moment bounds are stronger that exponential bounds. You know that, for any $p \geq 0$ and any $t > 0$:

$$\mathbb{P} (|X| \geq t) \leq \frac{\mathbb{E} (|X|^p)}{t^p}.$$

These bounds are stronger that the Chernoff bounds: if you know each of the moments of $X$, then the moment bounds allow you to get better bounds on $\mathbb{P} (|X| \geq t)$ than Chernoff bounds. However, they behave very badly when you look at sums of i.i.d. random variables (because the moments change in a non-trivial way), while the exponential bounds are very easy to manage:

$$\mathbb{E} (e^{\lambda S_n}) = \mathbb{E} (e^{\lambda X})^n.$$

==========

2) Obviously, Chernoff bounds exist as soon as the characteristic function $\mathbb{E} (e^{\lambda X})$ is defined on a neighborhood of $0$, so you only need exponential tails for $X$ (and not boundedness). Moreover, if you want to get a bound in one direction (i.e. on $\mathbb{P} (S_n/n \geq \varepsilon)$ or $\mathbb{P} (S_n/n \leq -\varepsilon)$, not on $\mathbb{P} (|S_n/n| \geq \varepsilon)$), you only need exponential tails in the corresponding direction.

If you assume stronger hypotheses on the tails of $X$, you can get stronger Chernoff bounds. Boundedness or sub-gaussianity of $X$ are typical assumptions.

You can get similar bounds (concentration inequalities) not only for the aprtial sums of i.i.d. random variables, but also for some martingales (see Collin McQuillan's answer), and for much, much larger classes of processes. This Wikipedia page will give you a taste of it, as well as some key-words, if you are interested.

-
1. It's a quantitative version of the central limit theorem, in addition to some bounds on tail probabilities the normal distribution. You can see that the normal distribution decays rapidly from the probability density function $\frac{1}{\sqrt{2\pi}}e^{-x^2/2}$. This leaves the question of an intuitive explanation for the central limit theorem. If something like the CLT were true, you would expect the probability distribution of $\frac{1}{\sqrt{n}}(X_1+\dots,X_n)$ (where $X_1,\dots,X_n$ are i.i.d.r.v with mean zero and bounded, say) to converge to a probability distribution whose moment generating function satisfies $M_X^n(t/\sqrt{n})=M_X(t)$, which must be of the form $\log M_X(t)=Ct^2$, and therefore must be a normal distribution.

2. It suffices that the variables are independent and bounded. An important generalisation is Azuma's inequality.

-

The way I see them, they are kind of generalization of Markov's inequality:

$$P(|X| \geq t ) \leq \frac{E|X|}{t}.$$

Observe, that here you use just a single moment, i.e. the expected value. To get a stronger bound, you could use two moments, i.e. Chebyshev's inequality:

$$P(|X-EX| \geq t) \leq \frac{D^2X}{t^2}.$$

This can be generalize to higher moments, fourth, sixth, and so on. Chernoff bound uses logarithmic number of moments, this is possible because you have $n$ i.i.d. random variables, so their sum is very concentrated around their mean. Please note that this just my intuition (it might be very wrong), sorry I can't provide any hard evidence.

Hope that helps :-)

-