Chernoff Bound

Exponentially tight tails for sums of independent bounded RVs.

The idea

Theorem (Chernoff bound (multiplicative form)).

Let $X = X_{1} + \cdots + X_{n}$, where the $X_{i}$ are independent and each takes only the values $0$ and $1$, and let $\mu = \mathbb{E}[X]$. Then for every $\delta \in (0, 1]$, $\mathbb{P}(X \geq (1+\delta)\mu) \leq e^{-\mu\delta^{2}/3}.$

The bound measures the deviation as a fraction of the mean, which is why the form is called multiplicative: $\delta = 0.5$ asks about overshooting $\mu$ by half, whether $\mu$ is $10$ or $10$ million.

Markov's and Chebyshev's inequalities bound the same event, but their guarantees decay polynomially in the deviation. This bound decays exponentially in $\mu$, so doubling the number of trials squares it rather than halving it. The analysis of randomized algorithms rests on this rate: it drives the probability of a wrong answer below any tolerance after a modest number of trials.

Independence pays for the exponential rate: without it, no bound of this form holds.

Ways to work on it

• Walkthrough. Bound the upper tail of a coin-flip count via the moment generating function.
• Practice. Plug into the upper-tail bound e^- δ^2/3.
• Hardest. Bound the lower tail of a random sum.

Not sure where to start? Take the ten-question placement test.