The Chernoff Bound: Exponential Tail Estimates

The precise statement

The Chernoff bound in its most general form is a one-line consequence of Markov's inequality. Let X be a real random variable whose moment generating function M(λ) = E[e^λX] is finite for λ in some interval containing 0. Then for every a ∈ ℝ and every λ > 0,

• ℙ(X ≥ a) ≤ e^−λa E[e^λX].

Since this holds for all λ > 0, we optimize: ℙ(X ≥ a) ≤ inf_λ>0 e^−λa M(λ). Writing ψ(λ) = log M(λ) for the cumulant generating function, the exponent is the Legendre–Fenchel transform ψ*(a) = sup_λ>0 (λa − ψ(λ)), so ℙ(X ≥ a) ≤ e^−ψ*(a).

The power appears when X = ∑ᵢ Xᵢ is a sum of independent variables: then M(λ) = ∏ᵢ Mᵢ(λ), the MGF factorizes, and the exponent grows linearly in the number of summands. This is what converts a per-variable bound into an exponentially small tail for the whole sum.

The intuition: why exponentials beat moments

Chebyshev's inequality uses one number — the variance — to control the tail, and a single moment can only give polynomial decay 1/t². The moment generating function E[e^λX] instead packages all the moments at once, since e^λX = ∑_k λ^kX^k/k!. Bounding the tail with this function therefore uses infinitely much information about the distribution.

Geometrically, the map x ↦ e^λx is convex and grows explosively. When you push the tail event {X ≥ a} through it, the region beyond a gets weighted by an enormous factor e^λa, so even a tiny probability there makes a visible contribution to E[e^λX]. Turning this around, if E[e^λX] is finite, the tail probability must be exponentially small — otherwise the expectation would blow up.

• The free parameter λ is a zoom knob: small λ probes the bulk, large λ probes the far tail. Optimizing over λ tunes the exponential weighting to exactly the deviation a you care about.

The key idea of the proof

The entire mechanism is: exponentiate, then apply Markov. For λ > 0 the event {X ≥ a} is identical to {e^λX ≥ e^λa}, because x ↦ e^λx is strictly increasing. Now e^λX is a nonnegative random variable, so Markov's inequality ℙ(Y ≥ c) ≤ E[Y]/c applies:

• ℙ(X ≥ a) = ℙ(e^λX ≥ e^λa) ≤ E[e^λX] / e^λa = e^−λa M(λ).

That is the whole bound for a fixed λ. Two refinements complete it. First, optimize over λ: because the inequality holds for every λ > 0, take the infimum. Second, for a sum of independent X₁,…,Xₙ, independence gives E[e^λ∑Xᵢ] = ∏ᵢ E[e^λXᵢ], so the log-bound is additive. The cleverness is not any single step but the choice of the exponential test function e^λx, whose multiplicativity mates perfectly with independence — the same idea underlies large-deviations theory and Cramér's theorem.

Worked example: fair coin flips

Let X = ∑_i=1ⁿ Xᵢ where the Xᵢ ∈ {0,1} are independent fair coin flips, so μ = E[X] = n/2. Each flip has MGF E[e^λXᵢ] = ½(1 + e^λ). We bound the upper tail ℙ(X ≥ (1+δ)μ). A standard specialization gives the clean multiplicative Chernoff bound:

• ℙ(X ≥ (1+δ)μ) ≤ [ e^δ / (1+δ)^(1+δ) ]^μ ≤ e^−μδ²/3 for 0 < δ ≤ 1.

Take n = 10,000, so μ = 5,000, and ask for ℙ(X ≥ 5,200), i.e. δ = 0.04. Chebyshev with σ² = n/4 = 2,500 gives only ℙ(X ≥ 5,200) ≤ 2,500/200² = 1/16 ≈ 0.0625. Chernoff gives e^{−5000·(0.04)²/3} = e^−8/3 ≈ 0.069 from the crude bound, and the exact optimized exponent uses n·D(0.52‖0.5) with the binary relative entropy D, giving ℙ(X ≥ 5,200) ≤ e^{−n·D(0.52‖0.5)} = e^{−10000·0.00080} ≈ e^−8.00 ≈ 3.3×10⁻⁴. The exponential form is what turns a hopeless polynomial estimate into a decisive one.

Why the hypotheses matter

The MGF must exist near 0. The bound is only useful where E[e^λX] < ∞ for some λ > 0. For a heavy-tailed distribution — say a Cauchy variable, or a Pareto with ℙ(X > x) ∼ x^−α — E[e^λX] = ∞ for every λ > 0, and the Chernoff method gives the vacuous bound ℙ(X ≥ a) ≤ ∞. Such tails genuinely decay only polynomially; no exponential estimate is possible, and Chebyshev is the best moment tool available.

• Independence is essential for the sum version: without it the MGF need not factorize. For dependent sequences you replace it with a martingale hypothesis, yielding Azuma–Hoeffding via the same exponential trick.
• Boundedness or a variance proxy is what pins down the rate: Hoeffding assumes aᵢ ≤ Xᵢ ≤ bᵢ (sub-Gaussian, e^−ct²); Bernstein and Bennett use the variance to get a sharper sub-exponential regime.

These relatives — Hoeffding (1963), Bernstein (1920s), Azuma (1967) — are all Chernoff's method with a distribution-specific MGF estimate plugged in.

Applications and significance

The Chernoff bound is the workhorse of the probabilistic method and of algorithm analysis. Because failure probabilities decay exponentially, a handful of extra repetitions crushes error to negligible levels — this is the engine behind:

• Randomized algorithms: amplifying a Monte Carlo algorithm's success probability, and load-balancing arguments (balls into bins, hashing) where you show no bin is overloaded except with probability n^−c.
• Learning theory: generalization and sample-complexity bounds, where you need the empirical average over m samples to concentrate around the true risk — the exponential rate yields the O((1/ε²)log(1/δ)) sample sizes in PAC learning.
• Random matrices and statistics: the matrix Chernoff bound (Ahlswede–Winter, Tropp) controls the spectrum of sums of independent random matrices; the union bound plus Chernoff underlies compressed sensing and dimension reduction (Johnson–Lindenstrauss).

Conceptually it is the finite-sample, quantitative counterpart of the law of large numbers and the entryway to Cramér's large-deviations principle, where the optimized exponent ψ*(a) becomes the exact rate function.

Chernoff versus other tail inequalities: what you assume and what you get for the deviation ℙ(|X − μ| ≥ t).

Inequality	Hypothesis needed	Tail bound (order)	Decay in t
Markov	X ≥ 0, finite mean	μ / a for ℙ(X ≥ a)	1/t (polynomial)
Chebyshev	Finite variance σ²	σ² / t²	1/t² (polynomial)
Chernoff (generic)	MGF E[e^{λX}] finite near 0	min_{λ>0} e^{−λa}E[e^{λX}]	exponential (rate set by MGF)
Hoeffding	Independent, aᵢ ≤ Xᵢ ≤ bᵢ	exp(−2t² / ∑(bᵢ−aᵢ)²)	e^{−ct²} (sub-Gaussian)
Bernstein	Independent, |Xᵢ| ≤ M, variance v	exp(−t² / (2v + 2Mt/3))	e^{−ct²} then e^{−ct} (sub-exponential)