The distribution of a sum of “small” random variables

Let $Y$ be a sum of many small random variables. For example, imagine that $Y$ is the number of heads in $n$ coin flips. The figure shows the typical distribution of such a sum around its expectation $\mu$. For $\varepsilon \in (0,1)$, the sum has probability about $e^{-\varepsilon ^2\mu }$ of deviating from $\mu$ by more than a factor of $1+\varepsilon$ (that is, an additive deviation of $\varepsilon \mu$).

For example (taking any $\varepsilon =\Theta (1/\sqrt\mu )$) the sum has constant probability of deviating from $\mu$ by an additive $\Theta (\sqrt\mu )$.

Or (taking $\varepsilon =\Theta (\sqrt{\log (n)/\mu })$), the sum has probability $n^{-\Theta (1)}$ of deviating from $\mu$ by more than $\Theta (\sqrt{ \mu \log n})$.

A typical Chernoff bound quantifies this behavior. It says that the event that $Y$ exceeds $1+\epsilon$ times its expectation $\mu$ is rare: it happens with probability at most $e^{-\mu \epsilon ^2/2}$. (A similar bound holds for $\Pr [ Y \le (1-\epsilon )\mu ]$.)

Example applications

Here are a couple of examples using a Chernoff bound.

Expectations of exponentials

The proof of the Chernoff bound for a sum $Y$ works by reasoning about the expectation of $(1+\varepsilon )^{Y}$. Here is some intuition for this approach. (For the full proof, go here.)

Recall the humble Markov bound: for any non-negative random variable $X$, the probability that $X$ exceeds $c$ is at most $E[X]/c$. This is useful but somewhat weak. Can we strengthen it by transforming $X$?

To take a concrete example, let $X_t$ be the number of heads in $t$ random coin flips. Consider $\textrm{E}[3^{X_t}]$. By direct calculation,

By induction, $\textrm{E}[3^{X_t}] = 2^t$.

Does this give anything useful? Applying the Markov bound to $3^{X_t}$ gives

For example, taking $t=100$ and $c=70$, we can conclude that the probability of getting $70$ or more heads in $100$ flips is at most about 5/10000. Choosing a base other than 3 may give a better bound.

The proof of the Chernoff bound generalizes this idea, and optimizes the base of the exponent. Typically, in order to bound the probability of deviating by a $1+\varepsilon$ factor from the mean, the best base for the exponent is something like $1+\varepsilon \approx e^\varepsilon$. To prove bounds on deviations below (as opposed to above) the mean, one uses a base less than 1. For most settings, these bounds are tight up to small constant factors in the exponent.