Chernoff bound

Statement

Let $X$ be a real random variable with moment-generating function $M_X(t) = E[e^{tX}]$, and let $a \in \mathbb{R}$. Then $$P(X \ge a) \le \inf_{t > 0} e^{-ta} M_X(t).$$

Remarks

Proof: for each $t > 0$, $\{X \ge a\} = \{e^{tX} \ge e^{ta}\}$. Markov's inequality gives $P(X \ge a) \le e^{-ta} E[e^{tX}]$. Then take the infimum over $t$. For a sum $S$ of independent $X_i$, $M_S = \prod_i M_{X_i}$. So the bound becomes $\inf_{t > 0} e^{-ta} \prod_i M_{X_i}(t)$, which decreases exponentially in many cases. For $S \sim \operatorname{Bin}(n, p)$ with mean $\mu = np$ and $0 < \delta$, a standard consequence is $P(S \ge (1 + \delta)\mu) \le \left(e^{\delta} / (1 + \delta)^{1 + \delta}\right)^{\mu}$.

History

The bound is named after Herman Chernoff.

Explanations

L1 human

The Chernoff bound gives tail estimates that decrease very fast, often exponentially. It is much stronger than Chebyshev's inequality for sums of many independent terms, such as the number of heads in many tosses.