Section
Large Deviations
Large deviation principles and rate functions
A large deviation principle (LDP) for a sequence of probability measures on a topological space (with its Borel -algebra) consists of a speed with and a rate function such that:
- for every closed set ,
- for every open set ,
A rate function on a topological space is a lower semicontinuous function that is not identically . Equivalently, for every , its sublevel set
is closed in .
A good rate function on a topological space is a rate function such that for every the sublevel set
is compact in .
Good rate functions are the natural large-deviation analogue of coercive “energy” functionals: they ensure that the variational problems appearing in a large deviation principle are attained on compact sets and interact well with exponential tightness. In metrizable settings (e.g. Polish spaces), goodness is often the key compactness hypothesis used to pass from bounds on nice sets to bounds on all Borel sets.
A sequence of probability measures on a topological space is exponentially tight at speed with if for every there exists a compact set such that
Exponential tightness is a strengthened form of ordinary tightness for probability measures: it not only forces most mass into compacts, but does so with exponentially small tails at the LDP speed. It is frequently paired with a rate function to obtain or upgrade a large deviation principle, and it is a standard hypothesis in results like the Gärtner–Ellis theorem.
A log moment generating function (log-MGF) of an -valued random variable is the function defined by
where is the Euclidean inner product and the expectation is taken in the sense of expectation.
A Cramér transform associated with a log moment generating function is the function defined by
This is the Legendre–Fenchel transform of (equivalently, the Fenchel conjugate of ).
A Laplace principle for a sequence of probability measures on a space , with speed and rate function , is the statement that for every bounded continuous function ,
Varadhan's lemma: Let be a Polish space and let be probability measures on that satisfy a large deviation principle with speed and good rate function . If is continuous and bounded above, then
Taking yields the Laplace principle. In many applications, the “goodness” of is obtained by combining an LDP with exponential tightness.
Cramér's theorem: Let be an i.i.d. sequence of real-valued random variables. Assume the moment generating function is finite for all in some open interval containing , and let be the log moment generating function. Define the empirical mean . Then satisfies a large deviation principle on with speed and good rate function
The rate function is the Cramér transform, i.e. the Legendre–Fenchel transform (Fenchel conjugate) of .
Sanov's theorem: Let be an i.i.d. sequence taking values in a Polish space , with common law . Define the empirical measure
viewed as a random element of (Borel probability measures on ) equipped with the topology of weak convergence. Then satisfies a large deviation principle on with speed and good rate function
Here is relative entropy (Kullback–Leibler divergence). Combined with the contraction principle, Sanov's theorem yields many LDPs for functionals of empirical measures.
Gärtner–Ellis theorem. Let be -valued random variables and let . Define the scaled log moment generating function
and assume the pointwise limit exists in for every . Suppose lies in the interior of the effective domain of , and that is lower semicontinuous and essentially smooth: it is differentiable throughout that interior and is steep at its boundary. Then satisfies a large deviation principle on with speed and good rate function
The function is the Legendre–Fenchel transform of . For empirical means of i.i.d. real variables, this recovers Cramér's theorem under standard regularity assumptions.
Contraction principle: Let be probability measures on a space that satisfy a large deviation principle with speed and rate function . Let be continuous, and let be the pushforward measures on . Then satisfies an LDP on with the same speed and rate function
with the convention .
In terms of random variables, if satisfies an LDP on and with continuous, then satisfies an LDP with rate obtained by minimizing over the fiber . This principle is routinely combined with Sanov's theorem and Cramér's theorem to derive LDPs for many statistics.