Lecture 9: Chernoff Bounds

Quick Overview

The Chernoff bound provides an exponentially small probability bound for how far a sum of mutually independent random variables strays from its expectation, significantly improving upon bounds like Chebyshev's by utilizing all higher moments, though its application critically depends on the assumption of mutual independence, as demonstrated by the misuse in complex financial products like CMOs.

Key Points: The Chernoff bound is presented as the "highest power tool" for tail bounds, utilizing the mutual independence of constituent random variables (assumed Bernoulli for the proof) and all higher moments, unlike Markov's (mean) or Chebyshev's (variance). The upper tail probability that X is larger than its mean mu by a $1+\delta$ factor decays exponentially in $n$, contrasting with the weak law of large numbers where it was only inverse polynomially small in $n$. The proof strategy hinges on applying Markov's inequality to the new non-negative random variable $Y = e^{bX}$, leading to the bound $\text{Prob}(X \ge a) \le E[e^{bX}] / e^{bA}$, where $E[e^{bX}]$ is the moment-generating function $mX(b)$. A key lemma states that for mutually independent $Xi$, the moment-generating function decomposes as a product: $mX(b) = \prod{i=1}^{n} m{Xi}(b)$. For a Bernoulli $Xi$ with $P(Xi=1)=pi$, its moment-generating function is bounded by $m{Xi}(b) \le e^{pi(e^b - 1)}$, which is derived from the inequality $1+y \le e^y$. The final upper tail bound is achieved by setting the threshold $a = (1+\delta)\mu$ and the helper parameter $b = \ln(1+\delta)$, resulting in the bound being at most $e^{-\frac{\mu \delta^2}{2+\delta}}$ after algebraic manipulation via Lemma 3.

Context: This lecture introduces the Chernoff bound as an advanced tool for bounding tail probabilities, building upon Markov's and Chebyshev's bounds by incorporating the structure of the random variable being a sum of mutually independent components. The discussion focuses on the "plain vanilla version" where the components $Xi$ are assumed to be independent Bernoulli random variables, leading to the definition of the mean $\mu$ as the sum of probabilities $pi$. The lecture dedicates significant time to detailing the complicated proof structure, which relies on the moment-generating function and properties derived from mutual independence.