Chernoff Bounds

Probability · Axiom Academy

Derive exponentially tight tail bounds using MGFs and apply them to sums of independent random variables 1. Markov's Inequality with MGF The key insight is to apply Markov's inequality to the exponential of a random variable. For any random variable X and any t > 0: By applying Markov's inequality to e^(tX) where t > 0: 2. Chernoff Bound for Sum of Independent RVs For independent random variables X₁, X₂, ..., Xₙ, let S = X₁ + X₂ + ... + Xₙ. The MGF of the sum is the product of individual MGFs: This allows us to bound P(S ≥ a) by minimizing over t > 0. For Bernoulli trials with success probability p, we get particularly clean bounds. For bounded random variables aᵢ ≤ Xᵢ ≤ bᵢ with mean E[Xᵢ] = μᵢ, Hoeffding's inequality states that for S = Σ Xᵢ with mean μ = Σ μᵢ: This bound is particularly useful because it only depends on the ranges of the random variables, not their distributions.

This is the written version of the interactive lesson above. See the full Probability course.