Chernoff Bounds — Mathematics Knowledge System

Overview

Chernoff bounds are exponentially tight tail bounds for sums of independent random variables. While Markov's and Chebyshev's inequalities give polynomial bounds (e.g., O(1/t²)), Chernoff bounds decay exponentially in the deviation t, making them far more powerful when the deviation is large relative to the standard deviation. The technique applies Markov's inequality to the moment generating function of the variable, then optimises over the free parameter. Chernoff-type bounds are the workhorse of probabilistic analysis in algorithms, combinatorics, and machine learning.

Intuition

The idea is: instead of bounding P(X ≥ a) directly, multiply both sides of X ≥ a by a positive number t to get tX ≥ ta, exponentiate to get e^{tX} ≥ e^{ta}, and then apply Markov's inequality (which requires non-negativity — here e^{tX} > 0 always). The resulting bound e^{−ta}·M_X(t) can then be minimised over t to get the tightest possible bound. The key insight is that the MGF of a sum of independent variables is the product of individual MGFs, allowing sharp bounds for sums.

Formal Definition

Definition

The general Chernoff bounding technique: for any random variable X and any t > 0:

P(X \geq a) = P(e^{tX} \geq e^{ta}) \leq \frac{E[e^{tX}]}{e^{ta}} = e^{-ta}\,M_X(t)

Chernoff bound via Markov's inequality (right tail)

P(X \geq a) \leq \inf_{t > 0}\, e^{-ta}\,M_X(t)

Optimised Chernoff bound

P\!\left(\sum_{i=1}^n X_i \geq (1+\delta)\mu\right) \leq \left(\frac{e^\delta}{(1+\delta)^{1+\delta}}\right)^\mu

Chernoff bound for sum of independent Bernoullis (mean μ, δ > 0)

P\!\left(\sum_{i=1}^n X_i \geq (1+\delta)\mu\right) \leq e^{-\mu\delta^2/3} \quad \text{for } 0 < \delta \leq 1

Simplified upper Chernoff bound (Bernoulli case)

Worked Examples

1
Write 60 = (1+δ)μ = (1+δ)·50, so δ = (60/50) − 1 = 0.2.
$1 + \delta = \frac{60}{50} = 1.2 \implies \delta = 0.2$
2
Apply the simplified bound with δ = 0.2 and μ = 50.
$P(X \geq 60) \leq e^{-\mu \delta^2/3} = e^{-50 \cdot (0.04)/3} = e^{-2/3} \approx e^{-0.667} \approx 0.513$
3
This is a valid upper bound, though loose. The exact probability (from binomial tables) is about 0.028, illustrating that bounds can be conservative.

✓ Answer

P(X ≥ 60) ≤ e^{−2/3} ≈ 0.51 (the exact value is much smaller, ≈ 0.028).

Practice Problems

Mediumfree response

Let X ~ Poisson(10). Use the Chernoff bound to bound P(X ≥ 20). The MGF of Poisson(λ) is M(t) = exp(λ(eᵗ−1)).

Mediumfree response

Why are Chernoff bounds exponentially tighter than Chebyshev bounds for large deviations?

Quiz

Summary

Chernoff bounds give exponentially decaying tail probabilities by applying Markov's inequality to e^{tX} and optimising over t.
The bound P(X ≥ a) ≤ inf_{t>0} e^{−ta}·M_X(t) is far tighter than Chebyshev for large deviations.
For sums of independent Bernoullis with mean μ: P(X ≥ (1+δ)μ) ≤ e^{−μδ²/3} (for 0 < δ ≤ 1).
Chernoff bounds are essential in algorithm analysis and combinatorics for showing that random outcomes concentrate tightly.

References

WebsiteWikipedia — Chernoff bound