Large Deviations — Mathematics Knowledge System

Overview

Large deviation theory quantifies the exponential rate at which probabilities of rare events decay. While the law of large numbers says (1/n)*sum X_i -> mu a.s. and the CLT describes fluctuations of order 1/sqrt(n), large deviations describes the probability that the average deviates from mu by a fixed amount: P((1/n)*sum X_i >= mu + epsilon) ~ e^{-n*I(mu + epsilon)} where I is the rate function. The Cramer theorem (1938) is the foundational result; Sanov's theorem extends it to empirical distributions; the Gartner-Ellis theorem handles dependent sequences via the log-moment generating function.

Intuition

You flip a fair coin 1000 times. Getting 600+ heads is unlikely -- the CLT says fluctuations of size 100 from the mean are extremely rare. But HOW rare? Not just 'very unlikely' -- exponentially unlikely: P(sum >= 600) ≈ e^{-1000 * I(0.6)} where I(x) = x*log(x/0.5) + (1-x)*log((1-x)/0.5) is the rate function (relative entropy of Bernoulli(x) vs Bernoulli(0.5)). Large deviations gives the precise exponential rate and reveals that the rate function is the Legendre-Fenchel transform of the log-moment generating function.

Formal Definition

Definition

A sequence of probability measures (mu_n) on a Polish space X satisfies a large deviation principle (LDP) with rate function I: X -> [0, inf] and speed n if: (1) I is lower semicontinuous, (2) for each closed F: limsup (1/n) log mu_n(F) <= -inf_{x in F} I(x), (3) for each open G: liminf (1/n) log mu_n(G) >= -inf_{x in G} I(x). Cramer's theorem: for i.i.d. X_i with moment generating function M(t) = E[e^{tX}] < inf near 0, the empirical means (1/n)*sum X_i satisfy LDP with rate I(x) = sup_t (t*x - log M(t)) (Legendre-Fenchel transform).

I(x) = \sup_{t \in \mathbb{R}} \{tx - \log M(t)\} = \sup_t \{tx - \log \mathbb{E}[e^{tX}]\}

Cramer rate function (Legendre-Fenchel transform)

\lim_{n\to\infty} \frac{1}{n}\log P\!\left(\frac{X_1+\cdots+X_n}{n} \ge a\right) = -I(a)

Cramer's theorem

I(Q) = D_{\mathrm{KL}}(Q \| P) = \mathbb{E}_Q\!\left[\log\frac{dQ}{dP}\right]

Sanov's rate function = KL divergence

\Lambda(t) = \lim_{n\to\infty} \frac{1}{n} \log \mathbb{E}[e^{t S_n}],\quad I = \Lambda^*

Gartner-Ellis theorem: I = Legendre transform of log-MGF

Notation

Notation	Meaning
$I(x)$	Rate function
$\Lambda(t)$	Cumulant generating function / log-moment generating function
$\Lambda^*(x)$	Legendre-Fenchel transform of Lambda
$D_{\mathrm{KL}}(Q\\|P)$	KL divergence from Q to P (rate function in Sanov)

Theorems

Theorem 1: Cramer's Theorem

Let X_1, X_2, ... be i.i.d. with log-moment generating function Lambda(t) = log E[e^{tX}] < inf in a neighborhood of 0. Then the empirical means S_n/n satisfy an LDP with speed n and good rate function I(x) = Lambda*(x) = sup_t(tx - Lambda(t)). In particular, P(S_n/n >= a) ≈ e^{-n*I(a)} for a > E[X].

Theorem 2: Sanov's Theorem

Let X_1, ..., X_n be i.i.d. with distribution P on a Polish space. The empirical distribution L_n = (1/n)*sum delta_{X_i} satisfies an LDP in the space of probability measures with speed n and rate function I(Q) = D_KL(Q || P) = integral log(dQ/dP) dQ if Q << P, and I(Q) = inf otherwise.

Theorem 3: Gartner-Ellis Theorem

Let Lambda(t) = lim (1/n) log E[e^{t*S_n}] exist (differentiably) for all t in R. Then S_n/n satisfies an LDP with rate function I = Lambda* (the Legendre-Fenchel transform of Lambda). This extends Cramer's theorem to dependent sequences (e.g., Markov chains).

Worked Examples

1
MGF: M(t) = E[e^{tX}] = (1 + e^t)/2 for X ~ Bernoulli(1/2).
$M(t) = \frac{1+e^t}{2}$
2
Rate function: I(x) = sup_t {tx - log(M(t))} = x*log(x) + (1-x)*log(1-x) + log 2 (computed by differentiating).
$I(x) = x\log(2x) + (1-x)\log(2(1-x))$
3
At x = 0.6: I(0.6) = 0.6*log(1.2) + 0.4*log(0.8) ≈ 0.6*0.1823 + 0.4*(-0.2231) ≈ 0.020.
$I(0.6) \approx 0.020$
4
P(S_n/n >= 0.6) ≈ e^{-n * 0.020}. For n = 1000: ≈ e^{-20} ≈ 2 * 10^{-9}.

✓ Answer

I(0.6) ≈ 0.020, so P(S_n/n >= 0.6) ≈ e^{-0.02*n}. For 1000 fair coin flips, the probability of getting 600+ heads is about 2 * 10^{-9}.

Practice Problems

Hardproof writing

Derive the rate function I(x) = x*log(x/mu) + (mu-x) for a Poisson(mu) random variable using the Legendre transform.

Common Mistakes

Common Mistake

Thinking large deviations is about the CLT scale of fluctuations.

The CLT describes deviations of order 1/sqrt(n) from the mean; large deviations describes fixed (order 1) deviations that are exponentially unlikely. The regimes are complementary: CLT is Gaussian on the 1/sqrt(n) scale, while LDP gives exponential rates for larger deviations.

Quiz

The rate function in Cramer's theorem is the Legendre-Fenchel transform of:

The probability density functionThe log-moment generating functionThe variance of XThe entropy of the distribution

Historical Background

The systematic theory of large deviations was founded by Cramer (1938) in his study of insurance ruin probabilities. Sanov (1957) extended the theory to empirical measures. Varadhan's abstract framework (1966) unified the theory and earned him the Abel Prize in 2007. Donsker and Varadhan (1975-83) developed the large deviation principle for Markov processes. The theory has applications to statistical mechanics (free energy = rate function), information theory (error exponents), and finance (risk management).

1938
Cramer proves the large deviations theorem for sums of i.i.d. random variables
Harald Cramer
1957
Sanov proves the large deviations for empirical distributions
I.N. Sanov
1966
Varadhan introduces the abstract large deviation principle
S.R.S. Varadhan
1975
Donsker and Varadhan develop LDP for Markov processes
Monroe Donsker, S.R.S. Varadhan

Summary

Large deviations quantifies exponential rates of rare events: P(S_n/n in A) ≈ e^{-n*inf_{x in A} I(x)}.
Cramer's theorem: rate function = Legendre-Fenchel transform of log-MGF.
Sanov's theorem: rate for empirical distributions = KL divergence to the true distribution.
Gartner-Ellis extends to dependent sequences via the cumulant generating function limit.

References

BookDembo, A. and Zeitouni, O. Large Deviations Techniques and Applications. Springer, 1998.
Bookden Hollander, F. Large Deviations. AMS, 2000.
WebsiteWikipedia -- Large deviations theory