Large Deviations & Tail Bounds

Let $X$ be a random variable whose moment-generating function $M_X(t) = \mathbb{E}[e^{tX}]$ is finite in a neighborhood of $0$. Then for any $a \in \mathbb{R}$:

For sums of independent random variables $S_n = X_1 + \cdots + X_n$ with iid summands, this becomes

Let $X_1, \ldots, X_n$ be iid Bernoulli$(p)$ and $S_n = \sum X_i$. The MGF of a single Bernoulli is $M(t) = 1 - p + p e^t$, so

where we’ve written the threshold as $np(1+\delta)$ for $\delta > 0$. The first-order condition $\Lambda'(t) = p(1+\delta)$ solves explicitly:

Substituting back, the Chernoff bound for the upper tail of a sum of iid Bernoullis is

For $p = 0.3, n = 100, \delta = 0.5$ (so threshold $= 45$), this gives a bound of about $0.0117$. The exact probability from the Binomial CDF is about $0.0068$ — the Chernoff bound is loose by less than a factor of two, while Chebyshev for the same event gives a bound of $\sigma^2 / (n (p\delta)^2) = (0.21/100) / (0.15)^2 \approx 0.093$, almost $14\times$ worse.

The Chernoff bound is tight in a precise asymptotic sense. Substituting the optimal $t^*$ gives the exponent

where $I(a) = \sup_t (ta - \Lambda(t))$ is the Cramér rate function. So the Chernoff bound for the iid sum is

and Cramér’s theorem (§12.6) says the bound is actually achieved at the exponential rate: $\lim_{n \to \infty} \frac{1}{n} \log P(\bar{X}_n \geq a) = -I(a)$. The Chernoff technique is the optimal exponential bound — nothing better is possible using the MGF alone.

Let $X$ be a random variable with $a \leq X \leq b$ almost surely and $\mathbb{E}[X] = 0$. Then for every $t \in \mathbb{R}$:

Let $X_1, \ldots, X_n$ be independent with $X_i \in [a_i, b_i]$ almost surely. Write $\mu_i = \mathbb{E}[X_i]$ and $\mu = \frac{1}{n}\sum_i \mu_i$. Then for every $\varepsilon > 0$:

and by symmetry

In the iid case with $X_i \in [a, b]$ for all $i$, this simplifies to the form previewed in Theorem 10.7:

You want to estimate the fraction of voters supporting candidate A to within $\varepsilon = 0.03$ with confidence $1 - \delta = 0.95$. Each response is a Bernoulli$(p)$ with unknown $p \in [0, 1]$. Hoeffding says:

That matches the “margin of error $\pm 3\%$ with 95% confidence, $n \approx 2000$” rule of thumb reported by polling organizations. The beauty of the Hoeffding derivation is that it’s distribution-free: it works for any $p$, doesn’t require estimating variance, and doesn’t rely on a normal approximation. Compare with Chebyshev, which would give $n \geq \sigma^2 / (\varepsilon^2 \delta) \leq 0.25 / (0.0009 \cdot 0.05) \approx 5{,}555$ — the factor of three difference we advertised in §12.1.

Hoeffding’s inequality uses only the range $[a, b]$, not the variance. For a Bernoulli$(p)$ with $p$ small, this is wasteful: the variance is $p(1-p)$, which can be much smaller than $(b-a)^2/4 = 1/4$. Hoeffding doesn’t care — it treats the worst-case range as though it always applied. This is sometimes exactly what you want (in PAC-learning scenarios where the distribution is unknown) and sometimes a real loss. Bernstein’s inequality (§12.4) fixes this by letting the bound shrink when the variance shrinks.

Let $X_1, \ldots, X_n$ be independent with $\mathbb{E}[X_i] = \mu$, $\text{Var}(X_i) = \sigma^2$, and $|X_i - \mu| \leq M$ almost surely. Then for every $\varepsilon > 0$:

Take $X_i \sim$ Bernoulli$(0.01)$, iid, $n = 1000$. Then $\mu = 0.01$, $\sigma^2 = 0.0099$, $M = 0.99$ (the deviation $|X_i - \mu|$ is at most $1 - 0.01 = 0.99$), $b - a = 1$. For $\varepsilon = 0.01$:

• Hoeffding: $2 \exp(-2 \cdot 1000 \cdot 0.0001 / 1) = 2 e^{-0.2} \approx 1.64$ — clamped to $1$; useless.
• Bernstein: $2 \exp\!\big(-\frac{1000 \cdot 0.0001}{2 \cdot 0.0099 + 2 \cdot 0.99 \cdot 0.01 / 3}\big) = 2 \exp(-0.1 / 0.02585) \approx 2 e^{-3.87} \approx 0.042$.

Bernstein gives a useful bound while Hoeffding gives nothing. The reason is the variance: when $p$ is small, $\sigma^2 = p(1-p) \approx p$ is much smaller than $(b-a)^2/4 = 0.25$. Bernstein exploits this; Hoeffding cannot.

Bernstein’s denominator $2\sigma^2 + 2M\varepsilon/3$ interpolates two behaviors. For small $\varepsilon$ (the sub-Gaussian regime), the $2\sigma^2$ term dominates and the exponent is $\approx -n\varepsilon^2/(2\sigma^2)$ — Gaussian-like tail decay with variance proxy $\sigma^2$. For large $\varepsilon$ (the sub-exponential regime), the $2M\varepsilon/3$ term dominates and the exponent is $\approx -3n\varepsilon/(2M)$ — exponential (not Gaussian) tail decay. The crossover happens around $\varepsilon \approx 3\sigma^2/M$. This two-regime behavior is exactly what we mean by a sub-exponential random variable, which we define next.

A random variable $X$ with $\mathbb{E}[X] = \mu$ is sub-Gaussian with parameter $\sigma \geq 0$ if for every $t \in \mathbb{R}$:

The parameter $\sigma$ is sometimes called the variance proxy. It need not equal the actual standard deviation of $X$.

A random variable $X$ with $\mathbb{E}[X] = \mu$ is sub-exponential with parameters $(\nu^2, b)$ (both positive) if for every $|t| < 1/b$:

Compared to the sub-Gaussian definition, the MGF bound only holds in a neighborhood of $t = 0$, not for all $t$. This allows heavier tails, but the tail probability decays only exponentially (not Gaussian) past a certain scale.

Let $X$ be a random variable with $\mathbb{E}[X] = \mu$. The following are equivalent (up to universal constants in the parameter):

1. MGF condition: $X$ is sub-Gaussian with parameter $\sigma$: $\mathbb{E}[e^{t(X - \mu)}] \leq e^{\sigma^2 t^2/2}$ for all $t$.
2. Tail condition: $P(|X - \mu| \geq u) \leq 2 e^{-u^2/(2\sigma^2)}$ for all $u \geq 0$.
3. Moment condition: $(\mathbb{E}[|X - \mu|^p])^{1/p} \leq C \sigma \sqrt{p}$ for all $p \geq 1$, with $C$ a universal constant.
4. Orlicz norm condition: $\|X - \mu\|_{\psi_2} < \infty$, where $\|Y\|_{\psi_2} = \inf\{c > 0 : \mathbb{E}[\exp(Y^2/c^2)] \leq 2\}$.

• Normal$(\mu, \sigma^2)$: The MGF is exactly $e^{\mu t + \sigma^2 t^2/2}$, so it is sub-Gaussian with parameter $\sigma$ — the variance proxy equals the actual standard deviation.
• Bounded $X \in [a, b]$: By Hoeffding’s lemma, $X$ centered is sub-Gaussian with parameter $(b-a)/2$. So every bounded random variable is sub-Gaussian, though the variance proxy may be loose.
• Rademacher $X \in \{-1, +1\}$: Sub-Gaussian with $\sigma = 1$. The key building block of Rademacher complexity.
• Exponential$(\lambda)$ centered at $1/\lambda$: Sub-exponential with parameters $(\nu^2, b) = (4/\lambda^2, 2/\lambda)$, but not sub-Gaussian — the right tail $P(X > t) = e^{-\lambda t}$ decays like $e^{-\lambda t}$ rather than $e^{-t^2}$.
• $\chi^2(1) - 1$: Sub-exponential but not sub-Gaussian. This matters: $\chi^2$ variables arise as squared Gaussians, and the square of a sub-Gaussian is always sub-exponential.
• Poisson$(\lambda)$ centered at $\lambda$: Sub-exponential, not sub-Gaussian.
• Cauchy$(0, 1)$: Has no finite mean, let alone a sub-Gaussian or sub-exponential MGF. Heavy-tailed. Concentration inequalities do not apply; even the LLN fails for Cauchy.
• Student-$t(\nu)$ for $\nu \geq 3$: Has finite variance but only polynomial tail decay. Not sub-exponential.

If $X_1, \ldots, X_n$ are independent and sub-Gaussian with parameters $\sigma_1, \ldots, \sigma_n$, then $\sum_i X_i$ is sub-Gaussian with parameter $\sqrt{\sum_i \sigma_i^2}$, and $\bar{X}_n$ is sub-Gaussian with parameter $\sigma/\sqrt{n}$ (in the iid case with common $\sigma$). The proof is a one-line MGF computation:

This is why sub-Gaussian is the right abstraction for statistical learning: every class closed under finite sums gives a rate that decays at the correct $1/\sqrt{n}$ scale. Apply the tail condition to $\bar{X}_n$ with variance proxy $\sigma^2/n$:

This is the sub-Gaussian form of the bound — cleaner than Hoeffding because it parametrizes by $\sigma$ rather than by $(b-a)$.

There is a strict hierarchy of tail classes:

Each inclusion is strict: a Normal is sub-Gaussian but not bounded; an Exponential is sub-exponential but not sub-Gaussian; a Student-$t(3)$ has finite variance but is not sub-exponential; a Cauchy has neither. Closure properties sit nicely on top: products of sub-Gaussians are sub-exponential (as in $\chi^2 = Z^2$), sums of sub-Gaussians are sub-Gaussian, maxima of finitely many sub-Gaussians are sub-Gaussian (with parameter scaled by $\sqrt{\log n}$). The Orlicz norm $\|X\|_{\psi_2}$ is a single number that controls the full tail behavior — Vershynin’s Chapter 2 develops this formalism in detail, and it’s the vocabulary of choice in high-dimensional statistics.

For a random variable $X$ with cumulant-generating function $\Lambda(t) = \log \mathbb{E}[e^{tX}]$ (finite in a neighborhood of $0$), the Cramér rate function is the Legendre transform of $\Lambda$:

The rate function is non-negative, convex, and vanishes at $x = \mathbb{E}[X]$.

Let $X_1, X_2, \ldots$ be iid with cumulant-generating function $\Lambda(t)$ finite in a neighborhood of $0$, and let $\mu = \mathbb{E}[X_1]$. Then for every $a > \mu$:

and for every $a < \mu$:

Equivalently, $P(\bar{X}_n \geq a)$ decays exponentially at the rate $I(a)$.

For $X_i \sim$ Bernoulli$(p)$, $\Lambda(t) = \log(1 - p + p e^t)$. The first-order condition $\Lambda'(t^*) = x$ becomes $p e^{t^*}/(1 - p + p e^{t^*}) = x$, which solves to $e^{t^*} = x(1-p)/[p(1-x)]$. Substituting:

So the large-deviation rate for a Bernoulli average deviating to $x$ is the Kullback–Leibler divergence between the empirical distribution Ber$(x)$ and the true distribution Ber$(p)$. This is not a coincidence — it is the Bernoulli case of Sanov’s theorem (next remark), which says the rate for the empirical measure is always the KL divergence.

For example, at $p = 0.3, x = 0.5$: $I(0.5) = 0.5 \log(5/3) + 0.5 \log(5/7) \approx 0.0872$, so $P(\bar{X}_n \geq 0.5) \lesssim e^{-0.0872 n}$. For $n = 100$ this is about $1.7 \times 10^{-4}$; the true binomial probability at $p = 0.3$ is about $1.8 \times 10^{-5}$. The Cramér rate captures the exponential order correctly; the sub-exponential prefactor (which Cramér does not capture) accounts for the remaining factor of $10$.

Sanov’s theorem generalizes Cramér from the scalar sample mean to the full empirical distribution. If $X_1, \ldots, X_n$ are iid from a distribution $P$ and $\hat{P}_n$ is the empirical measure (point masses at the observations), then for a “nice” set of distributions $\mathcal{Q}$ far from $P$:

In words: the rate at which the empirical distribution deviates to any fixed target $Q$ is the KL divergence between $Q$ and $P$. This is the information-theoretic interpretation of large deviations — rare events are improbable in proportion to how much information they would contain about the wrong distribution. The proof uses the method of types or topological machinery that we do not develop here; Dembo & Zeitouni (Chapter 6) is the standard reference. For our purposes, the Bernoulli case (Example 12.6) is the concrete instance that matters.

The rate function $I(x)$ is the Legendre transform of the cumulant-generating function $\Lambda(t) = \log M_X(t)$. For exponential families, $\Lambda(t)$ is the log-partition function (up to a shift in parameterization). So the rate function of an exponential-family sample mean is the conjugate of the log-partition function — a direct mathematical connection between large deviations and the exponential-family machinery of Topic 7. In Bayesian inference, this same conjugacy structure appears: the posterior concentrates around the MLE at the rate given by the KL divergence, and the quadratic approximation to $I(x)$ at the MLE is the Fisher information — the curvature of the log-likelihood. All of these are manifestations of the same Legendre duality.

Let $(M_0, M_1, \ldots, M_n)$ be a martingale with $|M_k - M_{k-1}| \leq c_k$ almost surely for each $k = 1, \ldots, n$. Then for every $t \geq 0$:

Let $f : \mathcal{X}^n \to \mathbb{R}$ be a function of $n$ variables satisfying the bounded-differences property with constants $c_1, \ldots, c_n$: for every $i$ and every $x_1, \ldots, x_n, x_i' \in \mathcal{X}$,

If $X_1, \ldots, X_n$ are independent random variables, then for every $t \geq 0$: