# Lecture 9: Chernoff Bounds

Source: https://www.youtube.com/watch?v=FPj3OOM6DEc
Recap page: https://rapidrecap.app/video/FPj3OOM6DEc
Generated: 2025-12-17T16:37:14.251+00:00

---
## 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 $m_X(b)$.
- A key lemma states that for mutually independent $X_i$, the moment-generating function decomposes as a product: $m_X(b) = \prod_{i=1}^{n} m_{X_i}(b)$.
- For a Bernoulli $X_i$ with $P(X_i=1)=p_i$, its moment-generating function is bounded by $m_{X_i}(b) \le e^{p_i(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 $X_i$ are assumed to be independent Bernoulli random variables, leading to the definition of the mean $\mu$ as the sum of probabilities $p_i$. The lecture dedicates significant time to detailing the complicated proof structure, which relies on the moment-generating function and properties derived from mutual independence.

## Detailed Analysis

The Chernoff bound provides an exponential decay rate for failure probabilities, making it superior to polynomial decay rates seen in weaker laws. The proof strategy begins by establishing that $\text{Prob}(X \ge a) = \text{Prob}(e^{bX} \ge e^{bA})$ for non-negative $b$, allowing the application of Markov's inequality to $Y=e^{bX}$ to yield an upper bound involving the moment-generating function $m_X(b) = E[e^{bX}]$. A crucial property exploited is that for mutually independent $X_i$, the moment-generating function factors into a product of individual moment-generating functions, $m_X(b) = \prod m_{X_i}(b)$. The proof then specifically estimates the moment-generating function for Bernoulli variables using the inequality $1+y \le e^y$, leading to $m_{X_i}(b) \le e^{p_i(e^b - 1)}$. By setting specific parameters $a$ and $b$ corresponding to the upper tail condition (where $a = (1+\delta)\mu$ and $b = \ln(1+\delta)$) and performing detailed algebraic manipulation involving logarithm bounds (Lemma 3), the final Chernoff upper tail bound is shown to be $\le e^{-\frac{\mu \delta^2}{2+\delta}}$. The lecturer emphasizes that while the proof is complex, understanding the modular architecture (Lemmas 1, 2, and 3) is key, and stresses that the assumption of mutual independence is absolutely critical, warning that misuse in scenarios like the 2008 financial crisis, where defaults on CMOs were assumed independent, leads to severe underestimation of risk.

### Tail Bound Comparison

- Markov uses non-negativity
- Chebyshev uses variance
- Chernoff uses mutual independence and higher moments
- Failure probability is exponentially small in $n$ for Chernoff.

### Proof Strategy Overview

- Apply Markov's inequality to $Y=e^{bX}$
- Right-hand side is the moment-generating function $m_X(b)$
- $m_X(b)$ decomposes into product of $m_{X_i}(b)$ due to mutual independence.

### Moment-Generating Function (MGF) Properties

- $m_X(b) = E[e^{bX}]$
- Series expansion reveals moments: coefficient of $b^i/i!$ is $E[X^i]$
- $E[X] = \frac{d}{db} m_X(b)
- _{b=0}$.

### Lemma 2 (Bernoulli MGF Bound)

- For $X_i$ Bernoulli with $P(X_i=1)=p_i$, $m_{X_i}(b) \le e^{p_i(e^b - 1)}$
- Derived using $1+y \le e^y$ on the exact expression $p_i e^b + (1-p_i) = 1 + p_i(e^b - 1)$.

### Setting Parameters for Upper Tail

- Threshold $a$ set to $(1+\delta)\mu$
- Helper parameter $b$ set to $\ln(1+\delta)$
- The final calculation relies on Lemma 3 bounding the resulting algebraic expression by $e^{-\frac{\mu \delta^2}{2+\delta}}$.

### Critical Caveat

- Mutual Independence Failure: Chernoff bound misuse occurred in 2008 financial crisis with CMOs
- Banks assumed default events were independent when they were economically dependent (domino effect)
- Knowing when tail bounds *don't* apply is as important as knowing how to use them.