Large Deviations

Large deviation theory measures how unlikely rare events are, showing that the probability of a sample average straying far from its mean decays exponentially fast at a rate fixed by a convex rate function.

Definition

A large deviation principle quantifies the exponential rate at which the probability of a rare event decays as a scaling parameter grows, through a lower semicontinuous rate function that assigns each outcome the exponential cost of observing it.

Scope

The topic covers the large deviation principle with its rate function and good rate functions, Cramer's theorem for sums of independent variables expressed through the Legendre transform of the cumulant generating function, the Gartner-Ellis theorem for dependent sequences, Sanov's theorem for empirical measures, the contraction principle, and Varadhan's integral lemma.

Core questions

• How fast does the probability of a sample average far from its mean decay?
• What is the rate function, and how is it computed from the underlying distribution?
• How do large deviation principles transform under continuous maps and integrals?
• How does the theory extend from independent sums to empirical measures and dependent processes?

Key concepts

• large deviation principle
• rate function
• Cramer's theorem
• Legendre transform
• contraction principle

Key theories

Cramer's theorem

For sums of independent identically distributed variables the empirical mean satisfies a large deviation principle whose rate function is the Legendre transform of the cumulant generating function, giving the exact exponential rate of decay for atypical averages.

Varadhan's integral lemma

Exponential integrals against a sequence satisfying a large deviation principle are governed asymptotically by a variational formula balancing the integrand against the rate function, the large-deviation analogue of Laplace's method and the route to free-energy computations.

Contraction principle

If a sequence obeys a large deviation principle and is mapped by a continuous function, the image obeys a large deviation principle whose rate function is obtained by minimizing the original rate function over preimages, transferring rates across changes of variable.

Clinical relevance

Large deviation rates quantify the probability of rare but consequential events: they bound buffer-overflow and packet-loss probabilities in communication networks, ruin probabilities in insurance, error exponents in information theory, and metastable transition rates in statistical physics and chemical kinetics.

History

Cramer obtained the exponential rate for sums of independent variables in 1938. Varadhan formulated the abstract large deviation principle in the 1960s and developed its calculus, work recognized with the Abel Prize, and Freidlin and Wentzell extended the theory to small-noise dynamical systems.

Key figures

• Harald Cramer
• S. R. Srinivasa Varadhan
• Mark Freidlin
• Alexander Wentzell

Seminal works

• dembo1998
• varadhan1984

Frequently asked questions

How does large deviation theory go beyond the central limit theorem?

The central limit theorem describes typical fluctuations on the scale of one over the square root of the sample size, whereas large deviation theory describes atypical fluctuations of order one, whose probabilities are exponentially small and are governed by the rate function rather than the Gaussian.

What is a rate function?

It is the non-negative function whose value at a point gives the exponential rate of decay of the probability of being near that point; it vanishes at the typical value and grows as outcomes become rarer, so minimizing it identifies the most likely way a rare event occurs.