Large deviations theory

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=\operatorname {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}}$, ${\displaystyle P(M_{N}>x)}$, that ${\displaystyle M_{N}}$ is greater than ${\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 \operatorname {E} [X_{i}]}$ unless ${\displaystyle N}$ is sufficiently large. Also, it does not provide information about the convergence of the tail probabilities as ${\displaystyle N\to \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={\tfrac {1}{2}}}$ and increases as ${\displaystyle x}$ approaches ${\displaystyle 1}$. It is the negative of the Bernoulli entropy with ${\displaystyle p={\tfrac {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))}$.[2] 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}$.[3] (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 \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.

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},\ldots }$ be independent and identically distributed (i.i.d.) random variables whose common distribution satisfies a certain growth condition. Then the following limit exists:

${\displaystyle \lim _{N\to \infty }{\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.[4][5]

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,[6]

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

where

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

is called the cumulant generating function (CGF) and ${\displaystyle \operatorname {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.

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}>xa_{N}]}$ for some sequence ${\displaystyle a_{N}\to 0}$. The following is an example of a moderate deviations principle:[7][8]

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

The rate function is related to the entropy in statistical mechanics. This can be heuristically seen in the following way. In statistical mechanics the entropy of a particular macro-state is related to the number of micro-states which corresponds to this macro-state. In our coin tossing example the mean value ${\displaystyle M_{N}}$ could designate a particular macro-state. And the particular sequence of heads and tails which gives rise to a particular value of ${\displaystyle M_{N}}$ constitutes a particular micro-state. Loosely speaking a macro-state having a higher number of micro-states giving rise to it, has higher entropy. And a state with higher entropy has a higher chance of being realised in actual experiments. The macro-state with mean value of 1/2 (as many heads as tails) has the highest number of micro-states giving rise to it and it is indeed the state with the highest entropy. And in most practical situations we shall indeed obtain this macro-state for large numbers of trials. The "rate function" on the other hand measures the probability of appearance of a particular macro-state. The smaller the rate function the higher is the chance of a macro-state appearing. In our coin-tossing the value of the "rate function" for mean value equal to 1/2 is zero. In this way one can see the "rate function" as the negative of the "entropy".

There is a relation between the "rate function" in large deviations theory and the Kullback–Leibler divergence, the connection is established by Sanov's theorem (see Sanov[11] and Novak,[13] ch. 14.5).

In a special case, large deviations are closely related to the concept of Gromov–Hausdorff limits.[14]