The distribution of a sum of “small” random variables

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

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

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

A typical Chernoff bound quantifies this behavior. It says that the event that $Y$Y exceeds $1+\epsilon$1+\epsilon times its expectation $\mu$\mu is rare: it happens with probability at most $e^{-\mu \epsilon ^2/2}$e^{-\mu \epsilon ^2/2}. (A similar bound holds for $\Pr [ Y \le (1-\epsilon )\mu ]$\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$Y works by reasoning about the expectation of $(1+\varepsilon )^{Y}$(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$X, the probability that $X$X exceeds $c$c is at most $E[X]/c$E[X]/c. This is useful but somewhat weak. Can we strengthen it by transforming $X$X?

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

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

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

For example, taking $t=100$t=100 and $c=70$c=70, we can conclude that the probability of getting $70$70 or more heads in $100$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$1+\varepsilon factor from the mean, the best base for the exponent is something like $1+\varepsilon \approx e^\varepsilon$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.