Large deviations theory

Roughly speaking, large deviations theory concerns itself with the exponential decline of the probability measures of certain kinds of extreme or tail events.

Introductory examples

Any large deviation is done in the least unlikely of all the unlikely ways!

— Frank den Hollander, Large Deviations, p. 10

An elementary example

Consider a sequence of independent tosses of a fair coin. The possible outcomes could be heads or tails. Let us denote the possible outcome of the i-th trial by ${\displaystyle X_i}$, where we encode head as 1 and tail as 0. Now let ${\displaystyle M_N}$ denote the mean value after ${\displaystyle N}$ trials, namely

${\displaystyle M_N=\frac{1}{N}\sum _{i=1}^N{X}_i}$.

Then ${\displaystyle M_N}$ lies between 0 and 1. From the law of large numbers it follows that as N grows, the distribution of ${\displaystyle M_N}$ converges to ${\displaystyle 0.5=\mathrm{E}[X]}$ (the expected value of a single coin toss).

Moreover, by the central limit theorem, it follows that ${\displaystyle M_N}$ is approximately normally distributed for large ${\displaystyle N}$. The central limit theorem can provide more detailed information about the behavior of ${\displaystyle M_N}$ than the law of large numbers. For example, we can approximately find a tail probability of ${\displaystyle M_N}$ – the probability that ${\displaystyle M_N}$ is greater than some value ${\displaystyle x}$ – for a fixed value of ${\displaystyle N}$. However, the approximation by the central limit theorem may not be accurate if ${\displaystyle x}$ is far from ${\displaystyle \mathrm{E}[X_i]}$ and ${\displaystyle N}$ is not sufficiently large. Also, it does not provide information about the convergence of the tail probabilities as ${\displaystyle N\to \mathrm{\infty }}$. However, the large deviation theory can provide answers for such problems.

Let us make this statement more precise. For a given value ${\displaystyle 0.5<x<1}$, let us compute the tail probability ${\displaystyle P(M_N>x)}$. Define

${\displaystyle I(x)=x\ln x+(1-x)\ln (1-x)+\ln 2}$.

Note that the function ${\displaystyle I(x)}$ is a convex, nonnegative function that is zero at ${\displaystyle x=\frac{1}{2}}$ and increases as ${\displaystyle x}$ approaches ${\displaystyle 1}$. It is the negative of the Bernoulli entropy with ${\displaystyle p=\frac{1}{2}}$; that it's appropriate for coin tosses follows from the asymptotic equipartition property applied to a Bernoulli trial. Then by Chernoff's inequality, it can be shown that ${\displaystyle P(M_N>x)<\exp (-NI(x))}$. This bound is rather sharp, in the sense that ${\displaystyle I(x)}$ cannot be replaced with a larger number which would yield a strict inequality for all positive ${\displaystyle N}$. (However, the exponential bound can still be reduced by a subexponential factor on the order of ${\displaystyle 1/\sqrt{N}}$; this follows from the Stirling approximation applied to the binomial coefficient appearing in the Bernoulli distribution.) Hence, we obtain the following result:

${\displaystyle P(M_N>x)\approx \exp (-NI(x))}$.

The probability ${\displaystyle P(M_N>x)}$ decays exponentially as ${\displaystyle N\to \mathrm{\infty }}$ at a rate depending on x. This formula approximates any tail probability of the sample mean of i.i.d. variables and gives its convergence as the number of samples increases.

Large deviations for sums of independent random variables

In the above example of coin-tossing we explicitly assumed that each toss is an independent trial, and the probability of getting head or tail is always the same.

Let ${\displaystyle X,X_1,X_2,\dots }$ be independent and identically distributed (i.i.d.) random variables whose common distribution satisfies a certain growth condition. Then the following limit exists:

${\displaystyle \underset{N\to \mathrm{\infty }}{lim}\frac{1}{N}\ln P(M_N>x)=-I(x)}$.

Here

${\displaystyle M_N=\frac{1}{N}\sum _{i=1}^N{X}_i}$,

as before.

Function ${\displaystyle I(\cdot )}$ is called the "rate function" or "Cramér function" or sometimes the "entropy function".

The above-mentioned limit means that for large ${\displaystyle N}$,

${\displaystyle P(M_N>x)\approx \exp [-NI(x)]}$,

which is the basic result of large deviations theory.

If we know the probability distribution of ${\displaystyle X}$, an explicit expression for the rate function can be obtained. This is given by a Legendre–Fenchel transformation,

${\displaystyle I(x)=\underset{\theta >0}{sup}[\theta x-\lambda (\theta )]}$,

where

${\displaystyle \lambda (\theta )=\ln \mathrm{E}[\exp (\theta X)]}$

is called the cumulant generating function (CGF) and ${\displaystyle \mathrm{E}}$ denotes the mathematical expectation.

If ${\displaystyle X}$ follows a normal distribution, the rate function becomes a parabola with its apex at the mean of the normal distribution.

If ${\displaystyle \{X_i\}}$ is an irreducible and aperiodic Markov chain, the variant of the basic large deviations result stated above may hold.

Moderate deviations for sums of independent random variables

The previous example controlled the probability of the event ${\displaystyle [M_N>x]}$, that is, the concentration of the law of ${\displaystyle M_N}$ on the compact set ${\displaystyle [-x,x]}$. It is also possible to control the probability of the event ${\displaystyle [M_N>x{a}_N]}$ for some sequence ${\displaystyle a_N\to 0}$. The following is an example of a moderate deviations principle:

Theorem — Let ${\displaystyle X_1,X_2,\dots }$ be a sequence of centered i.i.d variables with finite variance ${\displaystyle {\sigma }^2}$ such that ${\displaystyle \mathrm{\forall }\lambda \in \mathbb{R},\ln \mathbb{E}[e^{\lambda X_1}]<\mathrm{\infty }}$. Define ${\displaystyle M_N:=\frac{1}{N}\sum _{n\le N}{X}_N}$. Then for any sequence ${\displaystyle 1\ll a_N\ll \sqrt{N}}$:

${\displaystyle \underset{N\to +\mathrm{\infty }}{lim}\frac{a_N^2}{N}\ln \mathbb{P}[a_N{M}_N\ge x]=-\frac{x^2}{2{\sigma }^2}}$

In particular, the limit case ${\displaystyle a_N=\sqrt{N}}$ is the central limit theorem.