Large Deviations Theory

⚡ Key Takeaways

Large Deviations Theory quantifies the exponentially small probabilities of rare events: for a sequence of random variables, $P(\text{rare event}) \approx e^{-n I}$ where $n$ is a large parameter and $I \geq 0$ is the rate function. It applies wherever fluctuations away from typical behavior are governed by an exponential decay rate — statistical mechanics, queueing, information theory, and stochastic dynamics. Foundational work by Harald Cramér (1938), formalized by Varadhan (1966) and developed by Donsker–Varadhan and Freidlin–Wentzell.

💡 The Core Insight

Rare event probabilities decay exponentially, and the rate function $I$ measures the "cost" of each outcome. Among many ways a rare event could occur, the least improbable one dominates entirely — the probability is governed by $\inf_{x\in A} I(x)$ . This is a probabilistic analogue of Laplace's method: integrals concentrate at the minimizer of the exponent. The conjugate duality between the rate function $I$ and the cumulant generating function $\Lambda$ (via Legendre transform) is the unifying technical engine.

DefinitionLarge Deviation Principle

Let $\mathcal{X}$ be a Polish (complete separable metric) space with Borel $\sigma$ -algebra $\mathcal{B}$ . A family of probability measures $(\mu_\varepsilon)_{\varepsilon > 0}$ on $(\mathcal{X}, \mathcal{B})$ satisfies a large deviation principle (LDP) with rate function $I : \mathcal{X} \to [0, \infty]$ and speed $1/\varepsilon$ if $I$ is lower semicontinuous and for every Borel set $A$ :

1

\quad -\inf_{x \in A^\circ} I(x) \;\leq\; \liminf_{\varepsilon \to 0} \varepsilon \log \mu_\varepsilon(A) \;\leq\; \limsup_{\varepsilon \to 0} \varepsilon \log \mu_\varepsilon(A) \;\leq\; -\inf_{x \in \bar{A}} I(x)

where $A^\circ$ is the interior and $\bar{A}$ the closure of $A$ .

TheoremCramér's Theorem

Let $X_1, X_2, \dots$ be i.i.d. real random variables with logarithmic moment generating function

2

\quad \Lambda(\lambda) = \log \mathbb{E}\left[e^{\lambda X_1}\right], \qquad \lambda \in \mathbb{R},

finite in a neighborhood of the origin. Then the empirical means $S_n/n = \frac{1}{n}\sum_{i=1}^n X_i$ satisfy an LDP with speed $n$ and good rate function given by the Legendre–Fenchel transform

3

\quad I(x) = \Lambda^*(x) = \sup_{\lambda \in \mathbb{R}} \big(\lambda x - \Lambda(\lambda)\big).

TheoremVaradhan's Integral Lemma

If $(\mu_\varepsilon)$ satisfies an LDP with good rate function $I$ , and $F : \mathcal{X} \to \mathbb{R}$ is continuous and satisfies a tail (moment) condition, then

4

\quad \lim_{\varepsilon \to 0} \varepsilon \log \int_{\mathcal{X}} e^{F(x)/\varepsilon}\, d\mu_\varepsilon(x) \;=\; \sup_{x \in \mathcal{X}} \big(F(x) - I(x)\big).

TheoremGärtner–Ellis Theorem

Let $Z_\varepsilon$ be $\mathbb{R}^d$ -valued. Suppose the limiting log-MGF

5

\quad \Lambda(\lambda) = \lim_{\varepsilon \to 0} \varepsilon \log \mathbb{E}\left[e^{\langle \lambda, Z_\varepsilon\rangle / \varepsilon}\right]

exists as an extended real number for all $\lambda$ , is finite in a neighborhood of $0$ , lower semicontinuous, and differentiable in the interior of its domain (essential smoothness). Then $(Z_\varepsilon)$ satisfies an LDP with good rate function $I = \Lambda^*$ .

ProofCramér's Upper Bound via Chernoff

We sketch the upper bound of Cramér's theorem for a closed half-line $[x, \infty)$ with $x > \mu$ .

Step 1 (Exponential Markov / Chernoff). For any $\lambda \geq 0$ , by Markov's inequality applied to $e^{\lambda S_n}$ :

6

\quad P\left(\tfrac{S_n}{n} \geq x\right) = P\left(e^{\lambda S_n} \geq e^{\lambda n x}\right) \leq e^{-\lambda n x}\, \mathbb{E}\!\left[e^{\lambda S_n}\right] = e^{-n(\lambda x - \Lambda(\lambda))}.

Derivation hint: Independence gives $\mathbb{E}[e^{\lambda S_n}] = (\mathbb{E}[e^{\lambda X_1}])^n = e^{n\Lambda(\lambda)}$ ; Markov bounds the upper tail by the MGF.

Step 2 (Optimize over $\lambda$ ). Since the bound holds for all $\lambda \geq 0$ , take the infimum:

7

\quad P\left(\tfrac{S_n}{n} \geq x\right) \leq \exp\!\left(-n \sup_{\lambda \geq 0}\big(\lambda x - \Lambda(\lambda)\big)\right) = e^{-n I(x)}.

Derivation hint: For $x > \mu = \Lambda'(0)$ , the unconstrained sup over $\lambda \in \mathbb{R}$ is attained at some $\lambda^\star \geq 0$ , so the constrained and unconstrained suprema agree.

Step 3 (Lower bound via change of measure / tilting). Introduce the exponentially tilted (Esscher) measure $d\tilde{\mu}(y) = e^{\lambda^\star y - \Lambda(\lambda^\star)} d\mu(y)$ , chosen so that under $\tilde\mu$ the mean equals $x$ : $\tilde{\mathbb{E}}[X_1] = \Lambda'(\lambda^\star) = x$ . Then

8

\quad P\left(\tfrac{S_n}{n} \in (x-\delta, x+\delta)\right) = \tilde{\mathbb{E}}\!\left[ e^{-\lambda^\star S_n + n\Lambda(\lambda^\star)} \mathbf{1}_{\{S_n/n \in (x-\delta,x+\delta)\}}\right] \gtrsim e^{-n(\lambda^\star x - \Lambda(\lambda^\star)) - n\lambda^\star\delta}.

Derivation hint: Under the tilted law $S_n/n \to x$ by the LLN, so the indicator has probability $\to 1$ ; the Radon–Nikodym factor contributes the exponential rate. Letting $\delta \to 0$ matches the upper bound, yielding $I(x) = \Lambda^*(x)$ . The matching of upper and lower bounds at the same exponent $I(x) = \lambda^\star x - \Lambda(\lambda^\star)$ proves the LDP. $\blacksquare$

∎

mathematician · Harald Cramér | 1893–1985

Swedish actuary and probabilist who, motivated by insurance risk theory, derived the first sharp large-deviation estimates in his 1938 paper Sur un nouveau théorème-limite de la théorie des probabilités. Cramér sought to quantify the probability that aggregate insurance claims would exceed reserves — a genuinely rare but catastrophic event the CLT could not address. His exponential rate function, the Legendre transform of the cumulant generating function, became the prototype for the entire theory. Cramér also made foundational contributions to mathematical statistics (the Cramér–Rao bound) and stationary stochastic processes.

🧠 Intuition

Think of three nested descriptions of randomness, each finer than the last: 1. Law of Large Numbers: $S_n/n \to \mu$ . Tells you where the average lands. 2. Central Limit Theorem: $\sqrt{n}(S_n/n - \mu)$ is Gaussian. Describes $O(1/\sqrt n)$ fluctuations around $\mu$ . 3. Large Deviations: $P(S_n/n \approx x)$ for $x$ a fixed distance from $\mu$ decays like $e^{-nI(x)}$ . Describes the truly rare $O(1)$ excursions. The rate function $I$ is a "free energy" or "cost": $I(x) = 0$ at the typical value, and grows as you demand more atypical outcomes. The Legendre transform structure is exactly the Laplace/saddle-point principle: a sum of exponentials $\sum e^{n f_i}$ is dominated by its largest term. The tilting trick is the soul of the proof — to make a rare event likely, reweight the measure exponentially until that event becomes typical; the cost of reweighting is the rate function (it equals the relative entropy / Kullback–Leibler divergence between the tilted and original laws).

Figure

Rate function

I(x)

versus the moment generating function picture:

I

vanishes at the mean

\mu

and grows convexly; the slope

\lambda^\star(x)

is the optimal tilt.

ExampleCoin Flips: Probability of Excess Heads

Given. Fair coin, $X_i \in \{0,1\}$ with $P(X_i = 1) = 1/2$ . We seek the decay rate of $P(S_n/n \geq 0.75)$ , the probability of seeing $\geq 75\%$ heads in $n$ flips.

Step 1. Log-MGF: $\Lambda(\lambda) = \log \mathbb{E}[e^{\lambda X_1}] = \log\!\big(\tfrac12 + \tfrac12 e^\lambda\big)$ .

Step 2. Rate function via Legendre transform. For Bernoulli( $p$ ) the result is the binary relative entropy:

9

\quad I(x) = x \log\frac{x}{p} + (1-x)\log\frac{1-x}{1-p}, \qquad p = \tfrac12.

Derivation hint: Maximize $\lambda x - \log(\tfrac12 + \tfrac12 e^\lambda)$ ; set derivative to zero, solve $e^{\lambda^\star} = \frac{x(1-p)}{(1-x)p}$ , substitute back.

Step 3. Plug in $x = 0.75$ , $p = 0.5$ :

I(0.75) = 0.75 \log\frac{0.75}{0.5} + 0.25 \log\frac{0.25}{0.5} = 0.75(0.4055) + 0.25(-0.6931) = 0.3041 - 0.1733 = 0.1308 \text{ nats}.

Answer.

\boxed{P(S_n/n \geq 0.75) \approx e^{-0.1308\, n} \quad (\text{nats}); \text{ e.g. for } n=100,\; \sim e^{-13.08} \approx 2\times10^{-6}.}

ExampleGaussian Sample Mean

Given. $X_i \sim \mathcal{N}(0, \sigma^2)$ i.i.d. Find the rate function for $S_n/n$ and the probability $P(S_n/n \geq a)$ for $a > 0$ .

Step 1. Log-MGF of $\mathcal{N}(0,\sigma^2)$ : $\Lambda(\lambda) = \tfrac12 \sigma^2 \lambda^2$ .

Step 2. Legendre transform:

10

\quad I(x) = \sup_\lambda\left(\lambda x - \tfrac12 \sigma^2 \lambda^2\right) = \frac{x^2}{2\sigma^2}.

Derivation hint: The sup is attained at $\lambda^\star = x/\sigma^2$ ; substitute to get $x\cdot(x/\sigma^2) - \tfrac12\sigma^2(x/\sigma^2)^2 = x^2/(2\sigma^2)$ . The Legendre transform of a quadratic is the "reciprocal" quadratic.

Step 3. With $\sigma = 1$ , $a = 2$ : $I(2) = 4/2 = 2$ .

Answer.

\boxed{P(S_n/n \geq a) \approx e^{-n a^2/(2\sigma^2)}; \quad \sigma=1, a=2, n=50: \; e^{-100} \approx 4\times 10^{-44}.}

This matches the exact Gaussian tail: $S_n/n \sim \mathcal{N}(0, \sigma^2/n)$ , so the tail is $\exp(-n a^2/2\sigma^2)$ to leading exponential order. ✓

⚠️ The rate function is NOT the CLT variance

The Gaussian rate $I(x) = x^2/(2\sigma^2)$ looks like a CLT formula, but they describe different regimes. The CLT governs deviations of order $1/\sqrt n$ (the bulk), and is universal — it depends only on mean and variance. Large deviations govern deviations of order $1$ (the far tail), and are not universal — the full rate function depends on the entire distribution (all cumulants), not just the variance. Only for Gaussians do the two coincide because higher cumulants vanish. A common error is to extrapolate the CLT Gaussian approximation into the tail; this can be wrong by exponentially large factors.

CounterexampleHeavy tails: the LDP can fail entirely

Consider $X_i$ with a heavy (subexponential) tail, e.g. $P(X_1 > t) \sim t^{-\alpha}$ for some $\alpha > 1$ . Then the moment generating function $\mathbb{E}[e^{\lambda X_1}] = \infty$ for all $\lambda > 0$ , so $\Lambda(\lambda) = +\infty$ and Cramér's theorem does not apply. Worse, the rare-event mechanism changes completely: instead of all the summands deviating slightly (the "democratic" / collective scenario behind Cramér), the excess is caused by a single big jump — one $X_i$ alone reaches the large value. Consequently $P(S_n/n \geq x) \approx n\, P(X_1 \geq nx) \sim n^{1-\alpha} x^{-\alpha}$ decays only polynomially, not exponentially. This is the single big jump principle, the regime of "subexponential" or "catastrophe" distributions, where standard large deviations theory is replaced by extreme value heuristics.

connection · Entropy, thermodynamics, and information

The rate function in Sanov's Theorem for empirical distributions is precisely the Kullback–Leibler divergence (relative entropy) $H(\nu \| \mu) = \int \log(d\nu/d\mu)\, d\nu$ , making large deviations the rigorous probabilistic foundation of Statistical Mechanics. The Legendre duality between rate function and log-MGF mirrors the thermodynamic duality between entropy $S$ and free energy $F$ : $\Lambda$ plays the role of (scaled) free energy and $I$ the role of entropy, with $\lambda$ as inverse temperature. Varadhan's lemma is the rigorous Laplace/saddle-point method underlying partition-function asymptotics. Through the Gärtner–Ellis Theorem, large deviations extends to dependent processes such as Markov Chains, and via Freidlin–Wentzell Theory to small-noise Stochastic Differential Equations, where the rate function becomes an action functional minimized along an "instanton" path.

🔬 Where this appears

⏳ History

- 1877 — Ludwig Boltzmann relates entropy to the logarithm of microstate counts,

S = k\log W

, the physical seed of rate functions as entropy.

- 1923 — Filip Lundberg and Harald Cramér develop ruin theory in insurance, anticipating exponential decay of catastrophic events.

- 1938 — Harald Cramér's landmark paper establishes the first sharp large-deviation theorem for sums of i.i.d. random variables, introducing the Legendre transform of the log-MGF.

- 1952 — Herman Chernoff publishes his bound on tail probabilities, the workhorse exponential inequality central to statistics and computer science.

- 1957 — I. N. Sanov proves the large deviation principle for empirical measures, with relative entropy as the rate function.

- 1966 — S. R. Srinivasa Varadhan's seminal paper Asymptotic probabilities and differential equations formalizes the abstract LDP and proves his integral lemma, founding the modern theory.

- 1970s — Monroe Donsker and Varadhan develop the LDP for occupation measures of Markov processes (Donsker–Varadhan theory), with deep connections to spectral theory and the Feynman–Kac formula.

- 1970s–84 — Mark Freidlin and Alexander Wentzell create the theory of large deviations for small-noise stochastic differential equations, introducing the action functional and instanton (most-probable-path) analysis.

- 1984/1998 — Jürgen Gärtner and Richard Ellis develop the Gärtner–Ellis theorem; Amir Dembo and Ofer Zeitouni's textbook Large Deviations Techniques and Applications canonizes the field. Varadhan receives the Abel Prize in 2007 in part for this work.

open-problem · Beyond classical large deviations

Several frontiers remain active. (1) Non-convex and metastable systems: when rate functions are non-convex (mean-field models with phase transitions), the Legendre-transform approach via Gärtner–Ellis can fail to recover the true rate function — the convex dual only gives the convex hull, and resolving the full LDP requires finer tilted-measure or sub-additivity arguments. (2) Process-level and dynamical large deviations: establishing LDPs for the full empirical trajectory of interacting particle systems (hydrodynamic limits, the Macroscopic Fluctuation Theory of Bertini–De Sole–Gabrielli–Jona-Lasinio–Landim) and characterizing the associated quasi-potential remains technically formidable and often open in non-equilibrium settings. (3) Sharp asymptotics (Bahadur–Rao): the LDP gives only the exponential rate; obtaining the polynomial prefactor and exact constant $P \sim C n^{-1/2} e^{-nI(x)}$ for general distributions and dependent processes is subtle. (4) Heavy-tailed regimes: unifying the "collective" (Cramér) and "single big jump" (subexponential) mechanisms into one theory, and large deviations at intermediate scales (moderate deviations), is incompletely understood. (5) Empirical / data-driven rate functions: estimating rate functions from finite samples and constructing optimal importance-sampling schemes that provably achieve the LDP rate are open in high dimensions.

Formal Statement

Why It Holds / Derivation

Building Intuition

Worked Examples

Common Misconceptions

Connections

Real-World Applications

Historical Development

Subtleties & Limits

See Also