Fact-checked by Grok 2 weeks ago

Large deviations theory

Large deviations theory is a branch of probability theory that analyzes the exponential decay rates of probabilities for rare events in stochastic processes, particularly as a scaling parameter—such as the number of independent trials, system size, or time horizon—approaches infinity.^[1] It provides asymptotic estimates for the likelihood of significant deviations from typical behavior, such as those governed by the law of large numbers, where events with probability decaying like e^{-n I}, with n the scaling parameter and I > 0 the rate function, are quantified precisely.^[2] This framework is essential for understanding fluctuations in systems ranging from random walks to complex interacting particle models.^[3] The origins of large deviations theory trace back to Ludwig Boltzmann's 1877 calculation of the asymptotic behavior of multinomial probabilities using the relative entropy (now known as the Kullback-Leibler divergence), which linked rare fluctuations to the second law of thermodynamics in the context of statistical mechanics.^[4] In the early 20th century, Harald Cramér advanced the field through his 1938 theorem on the tail probabilities of sums of independent random variables, establishing a foundational large deviation principle for light-tailed distributions via the Legendre transform of the cumulant generating function.^[2] The modern formulation emerged in the 1960s and 1970s, largely through the work of Monroe Donsker and S. R. S. Varadhan, who developed the general large deviation principle (LDP) for empirical measures and diffusion processes, introducing the variational structure that unifies the theory across diverse settings.^[1] At its core, large deviations theory revolves around the large deviation principle, which states that for a sequence of probability measures \mathbb{P}_n, the probability of sets in a suitable space satisfies \lim_{n \to \infty} \frac{1}{n} \log \mathbb{P}_n(A) = -\inf_{x \in A} I(x), where I is a lower semicontinuous rate function that encodes the "cost" of deviation.^[3] Key results include Cramér's theorem for sums of i.i.d. random variables, Sanov's theorem for empirical distributions of Markov chains, and Varadhan's integral lemma, which connects LDPs to Laplace's method for asymptotics.^[2] These principles enable the study of phase transitions, concentration phenomena, and optimal control in stochastic systems.^[4] The theory finds broad applications in statistical physics, where it explains equilibrium and nonequilibrium phenomena like the Curie-Weiss model for ferromagnetism and large-scale fluctuations in turbulent flows; in information theory and statistics, for hypothesis testing and model selection; and in engineering and finance, for risk assessment in queues, networks, and market crashes.^[1] Numerical methods, such as importance sampling, further extend its utility by simulating rare events efficiently.^[1] Overall, large deviations theory bridges microscopic randomness and macroscopic determinism, offering insights into the improbable yet impactful behaviors of complex systems.^[3]

Introductory Examples

Elementary Example

Large deviations theory concerns the study of rare events whose probabilities decay exponentially fast as the sample size grows large. A classic illustration is the sequence of independent tosses of a fair coin, where each toss results in heads or tails with equal probability 1/2.^[5] Consider the event that all n tosses yield heads, an outcome far removed from the typical proportion of about 1/2 heads expected by the law of large numbers. The probability of this event is exactly P_n = (1/2)^n, which decreases exponentially with n. For instance, when n = 1, P_1 = 0.5; for n = 10, P_{10} \approx 0.00098; and for n = 100, P_{100} \approx 7.9 \times 10^{-31}, rendering the event extraordinarily unlikely for large n. This exponential decay highlights that directly computing such minuscule probabilities becomes impractical as n increases, motivating a shift in focus to the rate at which the logarithm of the probability scales with n.^[2]^[5] To quantify this rate, consider the normalized logarithmic probability \frac{1}{n} \log P_n. For the all-heads event, \log P_n = n \log(1/2) = -n \log 2, so \frac{1}{n} \log P_n = -\log 2 \approx -0.693, which remains constant and negative as n \to \infty. In general, for atypical rare events, this limit converges to -I where I > 0 captures the "cost" or unlikelihood of the deviation per trial, providing a scale-invariant measure of rarity without needing to handle vanishingly small probabilities directly. This perspective extends naturally to the sum of indicator variables for heads, where deviations in the total count behave similarly.^[4]^[2]

Sums of Independent Random Variables

In the canonical setting of large deviations theory, consider a sequence of independent and identically distributed (i.i.d.) random variables X_1, X_2, \dots, X_n defined on a probability space, each with finite mean \mu = \mathbb{E}[X_1]. The partial sum is defined as S_n = \sum_{i=1}^n X_i, and the empirical mean is \bar{S}_n = S_n / n. While the law of large numbers ensures that \bar{S}_n converges almost surely to \mu as n \to \infty, large deviations concern the exponentially small probabilities of substantial deviations from this mean. Specifically, for any \epsilon > 0, the upper tail probability satisfies \mathbb{P}(\bar{S}_n \geq \mu + \epsilon) \leq \exp(-n I(\mu + \epsilon)), where I(\mu + \epsilon) > 0 is a positive rate that quantifies the exponential decay.^[6] This rough large deviation estimate can be established via the Chernoff bound technique, a fundamental method for deriving exponential tail inequalities. For any t > 0 and a > n\mu, Markov's inequality applied to the exponential transform yields

\mathbb{P}(S_n \geq a) \leq e^{-t a} \mathbb{E}[e^{t S_n}].

Exploiting independence, the expectation factors as \mathbb{E}[e^{t S_n}] = [\mathbb{E}[e^{t X_1}]]^n = M(t)^n, where M(t) = \mathbb{E}[e^{t X_1}] denotes the moment generating function of X_1, assumed to exist for t in some interval around 0. Optimizing the bound over t > 0 gives

\mathbb{P}(S_n \geq a) \leq \exp\left( -n \sup_{t > 0} \left[ t \frac{a}{n} - \log M(t) \right] \right),

establishing exponential decay with rate I(x) = \sup_{t > 0} [t x - \log M(t)] > 0 for x > \mu.^[7] An illustrative example arises with Bernoulli random variables, which model binary outcomes such as successes in independent trials. Let X_i \sim \text{Bernoulli}(p) for $0 < p < 1, so \mu = p and S_n \sim \text{Binomial}(n, p). The moment generating function is M(t) = 1 - p + p e^t. Applying the Chernoff bound to the deviation \mathbb{P}(S_n \geq n(p + \epsilon)) for \epsilon > 0 yields

\mathbb{P}(\bar{S}_n \geq p + \epsilon) \leq \inf_{t > 0} e^{-t n (p + \epsilon)} (1 - p + p e^t)^n = \exp\left( -n I(p + \epsilon) \right),

where the rate is I(p + \epsilon) = \sup_{t > 0} [t (p + \epsilon) - \log(1 - p + p e^t)] > 0. This explicit computation confirms the exponential decay and highlights how the rate function captures the rarity of deviations, with the fair coin case (p = 1/2) serving as a simple special instance.

Moderate Deviations

Moderate deviations occupy an intermediate regime in probability theory, bridging the central limit theorem (CLT) and large deviations by analyzing the probabilities of deviations that exceed the typical CLT scale of O(1/\sqrt{n}) but remain o(1) as n \to \infty. For the sample mean \bar{X}_n = S_n/n of i.i.d. random variables \{X_i\} with mean \mu and finite positive variance \sigma^2, this corresponds to events like P(\bar{X}_n - \mu > a_n), where a_n \to 0 and n a_n^2 \to \infty. In this scaling, the deviations a_n are larger than the CLT fluctuations but smaller than the fixed-\epsilon deviations of classical large deviations, allowing for a refined exponential approximation to probabilities that the CLT describes only polynomially.^[8] The asymptotic rate in moderate deviations is characterized by a quadratic form near the mean, reflecting the local Gaussian behavior of the distribution. Specifically, under suitable moment conditions on \{X_i\},

\frac{1}{n a_n^2} \log P(|\bar{X}_n - \mu| > a_n) \to -\frac{1}{2\sigma^2}

as n \to \infty, for sequences a_n satisfying the above conditions. This rate links directly to the second-order Taylor expansion of the large deviations rate function around \mu, which is quadratic: I(x) \approx (x - \mu)^2 / (2\sigma^2) for x near \mu. The result holds for bounded or sub-Gaussian random variables, and extensions exist for heavier-tailed distributions with finite variance.^[8]^[2] In the example of sums of i.i.d. random variables with finite variance, moderate deviations recover the tail asymptotics of the CLT in exponential form. For instance, if \{X_i\} are standard normal, the exact probability P(\bar{X}_n > a_n) is asymptotically \exp(-n a_n^2 / 2) / (a_n \sqrt{2\pi n}), but the moderate deviations principle focuses on the leading exponential term \exp(-n a_n^2 / 2), ignoring the polynomial prefactor. This provides a uniform exponential estimate over a range of a_n where the CLT approximation would require large fixed quantiles, thus offering sharper logarithmic control for moderately rare events.^[8] Moderate deviations differ from large deviations in their decay rate: while large deviations probabilities decay exponentially fast at order n with a speed determined by a convex rate function I > 0 away from the mean, moderate deviations exhibit slower exponential decay governed by the scaling n a_n^2 \to \infty, resulting in rates that grow without bound but more gradually than in the fixed-deviation case. This intermediate regime is crucial for applications requiring precise tail bounds beyond the CLT, such as in statistical estimation and risk analysis, where events are unlikely but not asymptotically negligible on the large deviations scale.^[2]

Mathematical Foundations

Rate Functions

In large deviations theory, the rate function serves as the central object that encodes the exponential rate of decay for the probabilities of atypical events. Formally, a rate function I: X \to [0, \infty], where X is a topological space, is defined as a lower semicontinuous function.^[8] A rate function is termed "good" if, for every \alpha < \infty, the level set \{x \in X : I(x) \leq \alpha\} is compact; this ensures that the large deviation probabilities concentrate on compact regions, facilitating analytical tractability.^[1] Key properties of rate functions include non-negativity, I(x) \geq 0 for all x \in X, with equality holding uniquely at the typical or most probable point x_0, often the limit under the law of large numbers. Under conditions such as those arising from the Gärtner-Ellis theorem, rate functions exhibit strict convexity, which implies a unique minimizer and supports uniqueness in variational problems. These properties arise naturally in the context of exponential decay rates for rare events, as illustrated in basic examples of sums of random variables.^[8]^[1] Rate functions are commonly constructed via the Legendre-Fenchel transform of the scaled cumulant generating function (or log-moment generating function). Specifically, for a random variable X, let \Lambda(t) = \log \mathbb{E}[\exp(t X)] denote the cumulant generating function; the associated rate function is then given by

I(x) = \sup_{t \in \mathbb{R}} \left( t x - \Lambda(t) \right).

This transform, originating in Cramér's work on sums of independent random variables, yields a convex lower semicontinuous function that captures the large deviation behavior.^[8]^[1] Illustrative examples highlight the form of rate functions for simple distributions. For a Bernoulli random variable with success probability p \in (0,1), the rate function for the sample mean is the relative entropy (Kullback-Leibler divergence)

I(x) = x \log \frac{x}{p} + (1-x) \log \frac{1-x}{1-p}, \quad x \in [0,1],

which vanishes at x = p and grows logarithmically away from it. For a Gaussian random variable with mean \mu and variance \sigma^2 > 0, the rate function is quadratic:

I(x) = \frac{(x - \mu)^2}{2 \sigma^2}, \quad x \in \mathbb{R},

reflecting the parabolic decay of tail probabilities. These explicit forms demonstrate how rate functions adapt to the underlying distribution's structure.^[8]^[1]

Large Deviations Principle

The large deviations principle (LDP) formalizes the asymptotic behavior of rare events for sequences of probability measures on a topological space, capturing the exponential rate at which probabilities of atypical outcomes decay. Specifically, consider a sequence of probability measures \{\mu_n\}_{n \geq 1} on a Polish space \mathcal{X} (a complete separable metric space). The sequence \{\mu_n\} is said to satisfy the LDP with speed n and good rate function I: \mathcal{X} \to [0, \infty] (lower semicontinuous with compact level sets \{x \in \mathcal{X} : I(x) \leq \alpha\} for all \alpha < \infty) if, for every open subset O \subseteq \mathcal{X},

\liminf_{n \to \infty} \frac{1}{n} \log \mu_n(O) \geq -\inf_{x \in O} I(x),

and for every closed subset F \subseteq \mathcal{X},

\limsup_{n \to \infty} \frac{1}{n} \log \mu_n(F) \leq -\inf_{x \in F} I(x).

This formulation, known as the weak LDP, ensures control over probabilities via the topology's open and closed sets; the speed n normalizes the logarithmic probabilities, though more general speeds a_n \to \infty can be considered by replacing $1/n with $1/a_n.^[8] If the liminf and limsup inequalities hold for all Borel measurable sets (equivalently, when the rate function is good), the principle strengthens to the full or strong LDP, providing tighter uniformity.^[8] In practice, LDPs are classified by the complexity of the objects under study. A level-1 LDP typically governs the empirical mean \bar{X}_n = n^{-1} \sum_{i=1}^n X_i of i.i.d. random variables X_i in \mathbb{R}^d, yielding exponential decay rates for deviations from the law of large numbers. Level-2 LDPs extend this to the empirical measure L_n = n^{-1} \sum_{i=1}^n \delta_{X_i} on a space of probability measures, quantifying fluctuations in the sample distribution. Level-3 LDPs address higher-dimensional structures, such as empirical processes or path measures of stochastic processes, often in function spaces like Skorokhod space.^[8]^[9] To derive LDPs for transformed objects, the continuity principle applies: if \{X_n\} satisfies an LDP on \mathcal{X} with good rate function I, and f: \mathcal{X} \to \mathcal{Y} is continuous (where \mathcal{Y} is another Polish space), then \{f(X_n)\} satisfies an LDP on \mathcal{Y} with rate function J(y) = \inf\{I(x) : x \in \mathcal{X}, f(x) = y\}. The contraction principle generalizes this to measurable functions f, allowing LDPs to be projected onto subspaces or coarser observables while preserving the exponential scale, often reducing dimensionality in applications.^[8]

Historical Development

Early Foundations

The origins of large deviations theory trace back to early probabilistic insights into the behavior of sums of random variables and rare events, predating its formal mathematical development. A conceptual precursor emerged in the work of Jacob Bernoulli, who in 1713 articulated the law of large numbers in his seminal treatise Ars Conjectandi. This result established that the sample average of independent Bernoulli trials converges to the expected value as the number of trials increases, providing a foundation for understanding typical behavior but without addressing the exponential decay rates of atypical deviations.^[10] Bernoulli's theorem, while groundbreaking for its time, focused on convergence in probability rather than the precise quantification of improbable fluctuations, setting the stage for later refinements in asymptotic analysis. In the early 20th century, Alexander Khinchin advanced these ideas through his investigations into limit theorems for sums of independent random variables. In his 1933 monograph Asymptotische Gesetze der Wahrscheinlichkeitsrechnung, Khinchin derived early exponential estimates for the probabilities of large deviations from the mean in the context of the law of large numbers. These bounds quantified how the likelihood of significant departures decreases exponentially with the number of variables, offering initial tools for assessing rare events in probabilistic systems. Khinchin's contributions emphasized the role of moment-generating functions in obtaining such estimates, bridging classical limit laws with more refined asymptotic behaviors.^[11] Harald Cramér built directly on this foundation in 1938, motivated by practical problems in actuarial science. In his paper "Sur un nouveau théorème-limite de la théorie des probabilités," Cramér analyzed ruin probabilities for insurance companies modeled as sums of independent and identically distributed (i.i.d.) claims exceeding premiums. He established exponential upper bounds on the probability that the cumulative claims deviate substantially above the mean, deriving asymptotic expressions that decay exponentially with the initial capital. This work provided the first rigorous weak large deviation result for i.i.d. sums, highlighting the rate at which such ruin events become improbable as the scale increases.^[12] Cramér's approach, rooted in the cumulant-generating function, marked a pivotal step toward systematizing exponential tail behaviors. Parallel to these probabilistic developments, early applications in physics hinted at similar principles for rare fluctuations. Ludwig Boltzmann's 1877 derivation of the entropy formula in statistical mechanics involved asymptotic approximations for the probabilities of macroscopic states in large systems of particles. Specifically, in analyzing the equilibrium distribution, Boltzmann employed Stirling's approximation to show that deviations from the most probable state—corresponding to rare configurations—occur with probabilities exponentially small in the system size, governed by relative entropy differences. This insight, from his paper "Über die Beziehung zwischen dem zweiten Hauptsatz der mechanischen Wärmetheorie und der Wahrscheinlichkeitsrechnung," prefigured large deviation rates in thermodynamic contexts without the full probabilistic formalism.

Key Advancements

A pivotal advancement in the mid-20th century came from S. R. S. Varadhan, who in 1966 introduced an integral representation for rate functions, providing a foundational tool for deriving large deviation principles through Laplace-type integrals that capture the exponential decay of rare events. This work formalized the abstract framework for large deviations, extending beyond Cramér's early theorem on sums of independent variables to a broader class of stochastic systems. Building on this, Varadhan's 1984 monograph synthesized the disparate results into a unified theory, emphasizing variational principles and applications across probability and analysis.^[2] In the 1970s, Monroe D. Donsker and Varadhan extended the theory to functional large deviation principles for empirical processes, particularly occupation measures of Markov chains and diffusions, enabling the study of pathwise deviations in continuous-time settings. Their series of papers established rate functions in terms of principal eigenvalues of generators, bridging probabilistic limits with spectral theory. Concurrently, Mark Freidlin and Alexander D. Wentzell developed large deviation principles for stochastic processes with small noise perturbations, as detailed in their 1979 monograph (English edition 1984), focusing on exit times and quasipotentials in dynamical systems, which became essential for analyzing rare transitions in stochastic differential equations.^[13] The 1980s saw Richard S. Ellis connect large deviations to Gibbs measures in statistical mechanics, demonstrating how rate functions relate to free energy functionals and phase transitions in lattice systems. His contributions clarified the thermodynamic interpretation of large deviations, showing equivalence between variational problems in probability and entropy maximization in physical models.^[4] During the 1970s, researchers including Jacques Azéma, Hans Föllmer, and Daniel Stroock expanded the scope to martingales and processes in general Polish spaces, developing contraction principles and weak convergence criteria for non-i.i.d. sequences. These efforts generalized the large deviation principle to dependent structures, paving the way for applications in stochastic analysis. In the 1990s, further extensions incorporated rough path theory, initiated by Terry Lyons, to handle low-regularity paths in differential equations driven by noise; this remains an active area as of 2025, with ongoing refinements for multifractal processes and capacity-based deviations.^[14]

Core Theorems

Cramér's Theorem

Cramér's theorem establishes the large deviation principle for the sample mean of independent and identically distributed (i.i.d.) random variables under suitable moment conditions. Consider i.i.d. random variables X_1, X_2, \dots, X_n in \mathbb{R} with finite mean \mu = \mathbb{E}[X_1] and moment generating function M(t) = \mathbb{E}[e^{tX_1}] < \infty for all t in some open interval containing 0. The normalized sum \bar{X}_n = n^{-1} \sum_{i=1}^n X_i then satisfies a large deviation principle on \mathbb{R} with speed n and good rate function I: \mathbb{R} \to [0, \infty] given by

I(x) = \sup_{t \in \mathbb{R}} \left( t x - \log M(t) \right).

This rate function is lower semicontinuous, convex, and achieves the value 0 uniquely at x = \mu, with I(x) > 0 and finite for x \neq \mu in the effective domain where the supremum is finite. The proof of Cramér's theorem proceeds in two parts: establishing the upper and lower bounds of the large deviation principle. For the upper bound, fix x > \mu and t > 0 such that M(t) < \infty. By Markov's inequality applied to the exponential \mathbb{E}[e^{t(S_n - n x)}] \geq e^{t n (\bar{X}_n - x)} \mathbb{P}(\bar{X}_n \geq x), it follows that \mathbb{P}(\bar{X}_n \geq x) \leq e^{-n (t x - \log M(t))}. Optimizing over t > 0 yields \limsup_{n \to \infty} n^{-1} \log \mathbb{P}(\bar{X}_n \geq x) \leq -I(x), with a similar argument for the lower tail using t < 0. This establishes the large deviation upper bound for closed sets. The lower bound requires more care and is typically proved using a change-of-measure argument. For an open interval containing x > \mu where I(x) < \infty, introduce a new probability measure \mathbb{Q} via the Radon-Nikodym derivative d\mathbb{Q}/d\mathbb{P} = \frac{e^{t^* \sum_{i=1}^n X_i}}{M(t^*)^n} on the sigma-algebra generated by X_1, \dots, X_n, where t^* > 0 achieves the supremum in I(x). Under \mathbb{Q}, the X_i are i.i.d. with tilted distribution having mean x, so the law of large numbers implies \mathbb{Q}(\bar{X}_n \in U) \to 1 for any neighborhood U of x. Combined with a local central limit theorem to control the density of the tilted measure and the fact that \mathbb{P}(\bar{X}_n \in U) = \mathbb{E}_{\mathbb{Q}} \left[ e^{-t^* (S_n - n x)} \mathbf{1}_{\{\bar{X}_n \in U\}} \right] \approx e^{-n I(x)} on the event \{\bar{X}_n \approx x\}, this yields \liminf_{n \to \infty} n^{-1} \log \mathbb{P}(\bar{X}_n \in U) \geq -I(x). A symmetric argument holds for x < \mu. The assumption that M(t) is finite in a neighborhood of 0 ensures the rate function is steep and good, meaning its sublevel sets \{y : I(y) \leq \alpha\} are compact for all \alpha < \infty, which implies the large deviation principle holds for both open and closed sets. If the moment generating function is finite only on [0, \infty) or (-\infty, 0], one-sided versions of the theorem can be obtained by truncating the variables from below or above and passing to the limit, yielding a large deviation principle on half-lines. However, when the moment generating function is infinite everywhere except at 0—as occurs for heavy-tailed distributions like stable laws with index \alpha < 2—Cramér's theorem fails, and the probabilities of large deviations decay slower than exponentially, often dominated by the largest single term in the sum rather than collective behavior. A concrete illustration arises with the exponential distribution: let X_i \sim \operatorname{Exp}(1), so \mathbb{E}[X_i] = 1 and M(t) = (1 - t)^{-1} for t < 1. The cumulant generating function is \log M(t) = -\log(1 - t), and the rate function simplifies to

I(x) = \begin{cases} x - 1 - \log x & x > 0, \\ \infty & x \leq 0. \end{cases}

This explicit form shows I(x) growing linearly for large x, reflecting the light right tail of the exponential distribution, and confirms that deviations below 0 are impossible. The rate function I(x) can be recognized as the Legendre-Fenchel transform of \log M(t).

Sanov's Theorem

Sanov's theorem provides the large deviation principle for the empirical measures arising from independent and identically distributed (i.i.d.) random variables. Let X_1, \dots, X_n be i.i.d. random variables taking values in a Polish space (S, \mathcal{S}) with common probability measure \mu \in \mathcal{P}(S). The empirical measure is defined as

L_n = \frac{1}{n} \sum_{i=1}^n \delta_{X_i},

where \delta_x denotes the Dirac measure at x \in S. Then, the sequence \{L_n\}_{n \geq 1} satisfies a large deviation principle on the space \mathcal{P}(S) of probability measures on S, endowed with the topology of weak convergence, with speed n and good rate function

I(\pi) = \int_S \log \left( \frac{d\pi}{d\mu} \right) d\pi = H(\pi \Vert \mu)

for \pi \in \mathcal{P}(S) absolutely continuous with respect to \mu, and I(\pi) = +\infty otherwise; here, H(\cdot \Vert \cdot) denotes the relative entropy.^[15] The proof of Sanov's theorem typically proceeds in two parts. The upper bound follows from the contraction principle: the product measure on S^n satisfies an LDP with speed n and rate function I_n(x_1, \dots, x_n) = \sum_{i=1}^n \log \frac{d\mu}{d\nu}(x_i) for some reference \nu, and projecting onto the empirical measure yields the relative entropy rate after optimization. The lower bound relies on the structure of typical sets, where for closed sets away from \mu, the probability decays exponentially with rate given by the infimum of I, drawing from Sanov's original combinatorial argument using Stirling's approximation on multinomial probabilities in the finite-state case, extended via weak convergence to Polish spaces.^[16]^[15] Extensions of Sanov's theorem apply to dependent processes. For stationary ergodic Markov chains on a Polish state space, Donsker and Varadhan established an LDP for the empirical measure with rate function given by the Donsker-Varadhan functional I(\pi) = -\inf_{u > 0} \int \frac{L u}{u} \, d\pi, where L is the infinitesimal generator, capturing deviations in both the occupation measure and the transition structure of the chain.^[17] For non-i.i.d. sequences under absolutely continuous changes of measure, Girsanov's theorem facilitates the derivation of an LDP for empirical measures by tilting the reference dynamics, as used in models of interacting particles or diffusions.^[18] A concrete example illustrates the theorem for Bernoulli trials: let X_i \sim \mathrm{Bernoulli}(p) for $0 < p < 1, so \mu = p \delta_1 + (1-p) \delta_0. The empirical measure L_n on \{0,1\} has large deviations governed by I(\pi) = H(\pi \Vert \mu), and the proportion \hat{p}_n = L_n(\{1\}) follows an LDP with rate I(q) = q \log(q/p) + (1-q) \log((1-q)/(1-p)) for q \in [0,1], the binary relative entropy, linking to method-of-types estimates in information theory. This finite-dimensional projection corresponds to the level-1 large deviations in Cramér's theorem.

Varadhan's Lemma

Varadhan's lemma provides a fundamental variational representation for the asymptotic behavior of Laplace-type integrals under a large deviations principle (LDP). Suppose a sequence of probability measures \{\mu_n\} on a topological space X satisfies an LDP with speed n and good rate function I: X \to [0, \infty]. Then, for any bounded continuous function f: X \to \mathbb{R},

\lim_{n \to \infty} \frac{1}{n} \log \int_X \exp\bigl(n f(x)\bigr) \, \mu_n(dx) = \sup_{x \in X} \bigl( f(x) - I(x) \bigr).

This result, originally established by S.R.S. Varadhan in 1966, equates the scaled logarithmic moment-generating functional to the Legendre-Fenchel transform of the rate function and serves as a key tool for establishing upper bounds in LDPs.^[8] The proof of Varadhan's lemma proceeds in two parts: the upper and lower bounds. For the upper bound, the LDP's upper bound property is applied on compact level sets of the rate function, leveraging exponential tightness to control contributions from regions where I(x) is large; continuity and boundedness of f ensure the integral is dominated by points near the supremum. The lower bound relies on local approximations around points achieving the supremum, using the LDP's lower bound on small neighborhoods and the steepness of the good rate function to show that the integral grows at least as fast as \exp(n \sup (f - I)). These steps, detailed in standard treatments, confirm the limit under the given conditions.^[8] A converse to Varadhan's lemma holds: if \{\mu_n\} is exponentially tight and the limit equation is satisfied for all bounded continuous f, then \{\mu_n\} obeys an LDP with rate function I(x) = \sup_f \bigl( f(x) - \lim_{n \to \infty} \frac{1}{n} \log \int \exp(n f) \, d\mu_n \bigr). This equivalence underscores the lemma's role in characterizing LDPs via their logarithmic moment-generating functionals. Furthermore, the lemma facilitates proofs of contraction principles, where an LDP for a process induces an LDP for a continuous function of that process; the variational form allows direct computation of the induced rate function as an infimum over preimages.^[8] As an illustrative application, Varadhan's lemma derives the rate function for Sanov's theorem from a simpler LDP on finite-dimensional projections or function spaces. Consider i.i.d. random variables taking values in a finite set; an LDP for the joint empirical distribution on functions (e.g., via the Gärtner-Ellis theorem) yields, through the lemma's variational principle, the full large deviation rate for the empirical measure as the relative entropy with respect to the underlying distribution. This approach bypasses direct proofs and highlights the lemma's utility in extending LDPs across spaces.^[8]

Applications

Statistical Mechanics

In statistical mechanics, large deviations theory elucidates the probabilistic nature of rare fluctuations in particle systems, where the exponential decay rates of these events correspond directly to differences in free energy. For systems approaching thermodynamic equilibrium, the probability of observing a macroscopic state deviating from the typical equilibrium configuration scales as P(\mathcal{A}) \approx e^{-N I(\mathcal{A})}, with N denoting the system size and I(\mathcal{A}) the rate function, which often aligns with the excess free energy relative to the minimum. This connection arises because the rate function I is the Legendre-Fenchel transform of the scaled cumulant generating function, mirroring the free energy \phi(\beta) = \inf_u \{ \beta u - s(u) \}, where s(u) represents the entropy function for the fluctuating variable u. Such principles underpin the analysis of phase transitions and equilibrium properties in interacting particle systems.^[19] The Gibbs principle provides a foundational link between large deviations and the structure of Gibbs measures in lattice gas models, establishing a large deviations principle (LDP) for empirical measures that quantifies deviations from equilibrium distributions. In these models, the empirical measure L_N of particle occupations on a lattice satisfies an LDP with speed N and good rate function given by the relative entropy I(L_N | \mu) = \sum_x L_N(x) \log \frac{L_N(x)}{\mu(x)} with respect to the reference Gibbs measure \mu, ensuring concentration on minimizers that correspond to thermodynamic equilibrium states. This principle extends to interacting systems like the simple exclusion process, where hydrodynamic limits emerge, and rare fluctuations incur a large deviation cost proportional to the relative entropy, facilitating the study of macroscopic profiles in the thermodynamic limit.^[4]^[19] In nonequilibrium statistical mechanics, large deviations theory reveals fluctuation-dissipation relations through symmetries in the rate functions for entropy production in driven systems. The Evans-Searles fluctuation theorem asserts that for a dissipation function \Omega_t measuring irreversible work, the ratio of probabilities satisfies \frac{P(\Omega_t = A)}{P(\Omega_t = -A)} = e^{A}, implying a symmetry in the scaled cumulant generating function \lambda(k) = \lambda(1 - k) and thus in the rate function I(-w) - I(w) = w for the time-averaged entropy production rate w. Similarly, the Gallavotti-Cohen symmetry, applicable to steady-state currents in Markov processes, yields e(\lambda) = e(1 - \lambda) for the generating function of the action functional, leading to the rate function relation \hat{e}(w) - \hat{e}(-w) = -w, where the action relates to entropy production via local detailed balance conditions, such as W(t) = \beta \int_0^t J(s) \, ds for particle current J. These symmetries hold for driven lattice gases and diffusive systems, providing exact constraints on fluctuations far from equilibrium.^[20]^[21] A canonical example is the large deviations of empirical magnetization in the Ising model, which connects microscopic spin configurations to macroscopic order parameters and links to mean-field approximations like the Curie-Weiss model. In the ferromagnetic Ising model on a lattice, the empirical magnetization m_N = \frac{1}{N} \sum_i \sigma_i obeys an LDP with rate function I(m) = -s(m) + \beta h m - \phi(\beta, h), where s(m) = -\frac{1-m}{2} \log \frac{1-m}{2} - \frac{1+m}{2} \log \frac{1+m}{2} is the spin entropy and \phi the free energy; below the critical temperature, the rate function exhibits a double-well structure reflecting spontaneous magnetization. In the Curie-Weiss mean-field variant, where interactions are all-to-all, the LDP simplifies to a quadratic rate function near criticality, I(m) \approx \frac{(m - m_0)^2}{2 \chi}, with susceptibility \chi, enabling precise analysis of phase transitions and ensemble equivalence in the thermodynamic limit.^[19]^[4]

Information Theory

In information theory, large deviations theory provides a framework for analyzing the exponential decay rates of error probabilities in hypothesis testing, where Sanov's theorem characterizes the probability of empirical distributions deviating from the true distribution. Specifically, for distinguishing between two simple hypotheses with i.i.d. samples from distributions P and Q, the optimal type II error probability, under a fixed type I error constraint, decays exponentially with rate equal to the Kullback-Leibler (KL) divergence D(P \| Q), as established by the Chernoff-Stein lemma, whose proof relies on Sanov's theorem for the large deviation principle of empirical measures.^[22]^[23] For channel coding, large deviations principles underpin the achievability of reliable communication rates below channel capacity by quantifying the probability that codewords fall outside typical sets. The random coding error exponent E_r(R), which bounds the decay rate of the average error probability for random codes at rate R, can be derived using large deviations techniques applied to the output distributions induced by random codebooks, yielding E_r(R) = \sup_{0 \leq \rho \leq 1} \left[ E_0(\rho, P) - \rho R \right], where E_0(\rho, P) is the Gallager function involving the channel transition probabilities.^[24]^[25] This exponent highlights how deviations from the typical output set determine the reliability at finite block lengths. In source coding, large deviations theory addresses the exponential decay of compression errors when encoding i.i.d. sources at rates near or above the entropy. For fixed-rate lossless coding, the overflow probability—the chance that the empirical distribution requires more bits than allocated—obeys a large deviation principle with rate function given by the KL divergence from the source distribution, such that for a type \pi, the minimal rate is I(\pi) = D(\pi \| \mu), where \mu is the source pmf, linking directly to the source entropy as the infimum over such divergences.^[26] In the lossy setting, similar principles apply to the probability of exceeding a distortion threshold, with the rate-distortion function emerging as the minimal mutual information under large deviation constraints.^[22] A concrete example is the binary symmetric channel (BSC) with crossover probability \epsilon < 1/2, where the sphere-packing bound provides an upper bound on the error exponent that matches the random coding exponent at low rates. Using large deviations, the probability of atypical output spheres overlapping is analyzed via the deviation of the binomial output distribution from its mean, yielding the sphere-packing exponent E_{sp}(R) = D\left( \delta^* \| \epsilon \right) + (1 - h(\delta^*)) - R, where \delta^* solves a parametric equation balancing the entropy h(\cdot) and rate R, demonstrating the tight exponential error behavior for random codes.^[25]

Stochastic Processes

Large deviations principles for stochastic processes extend the theory to time-dependent paths and functionals, particularly for Markov processes and diffusions, where rare events involve atypical trajectories rather than static measures. In this context, the focus is on the exponential decay rates of probabilities for deviations in sample paths, often analyzed through controlled processes or variational problems. These principles are crucial for understanding long-time behaviors, exit problems, and system reliability in dynamic settings.^[27] A foundational framework is the Freidlin-Wentzell theory, which establishes a large deviations principle (LDP) for small-noise perturbations of deterministic dynamical systems. Consider a diffusion process satisfying the stochastic differential equation dX^\varepsilon_t = b(X^\varepsilon_t) \, dt + \sqrt{\varepsilon} \sigma(X^\varepsilon_t) \, dW_t, where b and \sigma are Lipschitz continuous functions, W_t is a standard Brownian motion, and \varepsilon > 0 is a small noise parameter. As \varepsilon \to 0, the rescaled process X^\varepsilon satisfies an LDP on the space of continuous paths with speed $1/\varepsilon and good rate function I(\phi) = \int_0^T L(\phi(t), \dot{\phi}(t)) \, dt, for absolutely continuous paths \phi: [0,T] \to \mathbb{R}^d with \dot{\phi} denoting the derivative, where the Lagrangian L(x,v) = \inf \{ \frac{1}{2} \|u\|^2 : v = b(x) + \sigma(x) u \} arises from an equivalent stochastic control problem. This rate function quantifies the "cost" of deviating from the deterministic flow \dot{x} = b(x), and the LDP enables precise asymptotics for pathwise rare events. The theory was developed in the seminal work by Freidlin and Wentzell, providing tools for analyzing metastability and noise-induced transitions in perturbed systems.^[27]^[28] For discrete-state Markov chains, sample path large deviations address the empirical behavior over long times. Specifically, for an irreducible continuous-time Markov chain on a countable state space with generator Q, the empirical measure \nu_n = \frac{1}{n} \int_0^n \delta_{X_t} \, dt satisfies an LDP as n \to \infty with speed n and rate function given by the Donsker-Varadhan functional H(\nu) = -\inf_{f > 0} \int \frac{Qf}{f} \, d\nu, where the infimum is over positive functions f vanishing on sets of \nu-measure zero. This variational form captures deviations from the invariant measure, with the rate reflecting relative entropy-like costs for atypical occupation distributions. Extensions to empirical flows, which track transition rates, yield joint LDPs for measures and flows, facilitating analysis of dynamic inconsistencies. The Donsker-Varadhan framework originated in their pioneering papers on asymptotic expectations for Markov processes.^[17] In queueing theory, large deviations for stochastic processes underpin tail probability estimates and many-server limits. For multiserver queues in the Halfin-Whitt regime, where the number of servers n grows with arrival rate \lambda_n = n + \beta \sqrt{n} for fixed \beta > 0, sample path LDPs describe rare overloads via Freidlin-Wentzell-type rates, often computed using tilted measures to shift the probability under which large queues become typical. Tilted measures, obtained by exponentially changing the underlying process distribution, simplify computations of \mathbb{P}(\sup_t Q_t > a n) \sim e^{-n I(a)} for queue length Q_t, revealing exponential decay with rate I(a) derived from controlled diffusions. These results extend to networks, providing bounds on workload tails and abandonment probabilities in high-dimensional systems. Seminal applications appear in analyses of G/GI/n queues with reneging.^[29] A illustrative example is the exit time of a small-noise Brownian motion from a domain. For the process X^\varepsilon_t = \sqrt{\varepsilon} W_t starting at 0, the probability of exiting a bounded domain D at point x \in \partial D before others satisfies \mathbb{P}(\tau_D < \infty, X^\varepsilon_{\tau_D} \approx x) \sim e^{-V(x)/\varepsilon} as \varepsilon \to 0, where \tau_D = \inf\{ t : X_t \notin D \} and the quasipotential V(x) = \inf \{ I(\phi) : \phi(0)=0, \phi(T)=x, \phi(s) \in D \ \forall s \} is the minimal action functional over connecting paths. For standard Brownian motion, V(x) = |x|^2 / 2, yielding explicit asymptotics for first-exit problems. This quasipotential governs the most likely exit mechanism under noise.^[27]

References

[1]
[1106.4146] A basic introduction to large deviations: Theory ... - arXiv
Jun 21, 2011 · The theory of large deviations deals with the probabilities of rare events (or fluctuations) that are exponentially small as a function of some parameter.
[2]
[PDF] LARGE DEVIATIONS
Introduction. The theory of large deviations deals with rates at which probabilities of certain events decay as a natural parameter in the problem varies.
[3]
[PDF] An Introduction to Large Deviations
Feb 16, 2021 · The large deviations theory is one of the key techniques of modern probability. It concerns with the study of probabilities of rare events and ...
[4]
None
### Summary of Historical Development and Key Contributions to Large Deviations Theory
[5]
[PDF] Special invited paper *13pt Large deviations - arXiv
The simplest example for which one can calculate probabilities of large deviations is coin tossing. The probability of k heads in n tosses of a fair coin is.Missing: flips | Show results with:flips
[6]
[PDF] On a new limit theorem in probability theory (Sur un nouveau théor ...
Aug 31, 2022 · The following is a translation of Harald Cramér's article,. “On a new limit theorem in probability theory”, published in. French in 1938 [7] ...
[7]
A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based ...
BY HERMAN CHERNOFF. University of Illinois and Stanford University. 1. Summary ... order to apply a bound on the error of the normal approximation to the dis-.Missing: original | Show results with:original
[8]
Large Deviations Techniques and Applications - SpringerLink
Amir Dembo and Ofer Zeitouni, two of the leading researchers in the field ... Available as PDF; Read on any device; Instant download; Own it forever. Buy ...
[9]
[PDF] Large deviations of empirical measures of diffusions in ... - arXiv
Sep 22, 2020 · Corollary 1 (Level 1 large deviations principle). ... This means that, for any neighborhood Iδ of I in the τκ-topology, the empirical measure ...
[10]
Jacobi Bernoulli profess. basil. & utriusque societ. ... Ars conjectandi ...
This book, published posthumously, was his greatest work in which he demonstrated the calculus of probability, the theory of combinations and permutations.
[11]
Asymptotische Gesetƶe der Wahrscheinlichkeitsrechnung
Free delivery 14-day returnsDieser Buchtitel ist Teil des Digitalisierungsprojekts Springer Book Archives mit Publikationen, die seit den Anfängen des Verlags von 1842 erschienen sind.
[12]
On a new limit theorem in probability theory (Translation of 'Sur un ...
Feb 16, 2018 · This is a translation of Harald Cramér's article, 'On a new limit theorem in probability theory', published in French in 1938.
[13]
On the probability of large deviations of random variables
Semantic Scholar extracted view of "On the probability of large deviations of random variables" by I. N. Sanov.
[14]
[PDF] A simple proof of Sanov's theorem*
Sanov's Theorem. For independent drawings from a distribution Q ∈ P, the empirical distributions of the resulting samples satisfy the large deviations principle ...Missing: sketch | Show results with:sketch
[15]
Large Deviations for the Empirical Measure of a Markov Chain ... - jstor
The main theorems in this paper prove uniform large deviation properties for the empirical measure and the multivariate empirical measure of a. Markov chain ...
[16]
The enhanced Sanov theorem and propagation of chaos
Indeed, combining Girsanov's theorem and Varadhan's lemma will then imply a LDP for the empirical measures, as n → ∞ , for the particle system given by (1.7) d ...
[17]
[0804.0327] The large deviation approach to statistical mechanics
Apr 2, 2008 · Abstract: The theory of large deviations is concerned with the exponential decay of probabilities of large fluctuations in random systems.
[18]
https://www.sciencedirect.com/science/article/pii/S0304414917302296
[19]
[cond-mat/9811220] A Gallavotti-Cohen Type Symmetry in the Large ...
Nov 16, 1998 · We extend the work of Kurchan on the Gallavotti-Cohen fluctuation theorem, which yields a symmetry property of the large deviation function, to general Markov ...
[20]
https://arxiv.org/abs/0709.3888
[21]
[PDF] A large deviations approach to error exponents in source coding ...
In this correspondence we discuss two basic communication- theoretic problems-the binary hypothesis testing problem and the source coding problem for finite ...
[22]
https://ieeexplore.ieee.org/document/53762
[23]
[PDF] On exponential error bounds for random codes on the BSC | MIT
In this note we will revisit the development of exponential error bounds for random codes on the binary symmetric channel (BSC). This is a very old problem, ...
[24]
[PDF] Source coding, large deviations, and approximate pattern matching
Abstract—In this review paper, we present a development of parts of rate-distortion theory and pattern-matching algorithms for lossy data compression, ...
[25]
Random Perturbations of Dynamical Systems - SpringerLink
In stock Free deliveryFront Matter. Pages I-XXVIII. Download chapter PDF · Random Perturbations. Mark I. Freidlin, Alexander D. Wentzell. Pages 1-28. Small Random Perturbations on a ...
[26]
[PDF] Large Deviations for Stochastic Differential Equations
As in Chapter 31, the strategy is to first prove a large deviations principle for a comparatively simple case, and then transfer it to more subtle processes.
[27]
[1904.04938] Many-Server Asymptotics for Join-the-Shortest-Queue
Apr 9, 2019 · Many-Server Asymptotics for Join-the-Shortest-Queue: Large Deviations and Rare Events. Authors:Amarjit Budhiraja, Eric Friedlander, Ruoyu Wu.