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 ,
In many applications, is the law of a sequence of random variables defined on a probability space. Additional structure such as a good rate function or exponential tightness often ensures useful compactness properties and helps upgrade “local” bounds to a full LDP.
A rate function on a topological space is a function that is lower semicontinuous, meaning that for every the sublevel set
is closed in , and such that is not identically .
Rate functions quantify the exponential scale of rare-event probabilities in a large deviation principle: heuristically, for large and speed . A particularly well-behaved class is given by good rate functions, whose sublevel sets are compact.
is a rate function; it forces mass to concentrate on at the exponential scale.
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 ,
This is the Laplace-transform formulation of the large deviation principle. Under standard hypotheses (for example, Polish and exponentially tight), the Laplace principle with a good rate function is equivalent to an LDP with the same rate 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 all . Suppose that is lower semicontinuous, its effective domain has nonempty interior, and is differentiable on the interior of its effective domain and steep (meaning whenever approaches the boundary of the effective domain). Then satisfies a large deviation principle on with speed and 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.