Large deviations theory

In probability theory, the theory of large deviations concerns the asymptotic behaviour of remote tails of sequences of probability distributions. Some basic ideas of the theory can be tracked back to Laplace and Cramér, although a clear unified formal definition was introduced in 1966 by Varadhan. Large deviations theory formalizes the heuristic ideas of concentration of measures and widely generalizes the notion of convergence of probability measures.

Roughly speaking, large deviations theory concerns itself with the exponential decay of the probability measures of certain kinds of extreme or tail events, as the number of observations grows arbitrarily large.

Introductory examples

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 $X_{i}$, where we encode head as -1 and tail as 1. Now let $M_{N}$ denote the mean value after $N$ trials, namely

$M_{N}:={\frac {1}{N}}\sum _{i=1}^{N}X_{i}$

Then $M_{N}$ lies between -1 and 1. From the law of large numbers (and also from our experience) we know that as N grows, $M_{N}$ becomes closer and closer to $0$ with increasing probability. Let us make this statement more precise. For a given value $0<x<1$, let us compute the probability $P(M_{N}>x)$ that $M_{N}$ is greater than $x$. Define

$I(x)={\frac {1}{2}}[(1+x)\log(1+x)+(1-x)\log(1-x)]$.

Then by Chernoff's inequality it can be shown that $P(M_{N}>x)<\exp(-NI(x))$. This bound is rather sharp, in the sense that $I(x)$ cannot be replaced with a larger number which would yield a true inequality for all positive $N$. (However, the exponential bound can still be reduced by a subexponential factor on the order of $1/{\sqrt {N}}$.) At any rate, the probability $P(M_{N}>x)$ is decaying exponentially rapidly as N grows large, at a rate depending on x.

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 for each toss, the probability of getting head or tail is always the same. This makes the random numbers $X_{i}$ independent and identically distributed (i.i.d.). For i.i.d. variables whose common distribution satisfies a certain growth condition, large deviation theory states that the following limit exists:

$\lim _{N\to \infty }{\frac {1}{N}}\log P(M_{N}>x)=-I(x)$

The function $I(x)$ is called the "rate function" or "Cramér function" or sometimes the "entropy function". Roughly speaking, the existence of this limit is what establishes the above mentioned exponential decay and allows us to conclude that for large $N$, $P(M_{N}>x)$ takes the form:

$P(M_{N}>x)\approx \exp[-NI(x)].$

which is the basic result of large deviations theory in this setting. Note that the inequality given in the first paragraph, as opposed to the asymptotic formula presented here, need not remain valid in more general settings.

In the i.i.d. setting, if we know the probability distribution of $X_{i}$, an explicit expression for the rate function can be obtained. This is given by a Legendre transform,

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

where the function $\lambda (\theta )$ is called the cumulant generating function (CGF), given by

$\lambda (\theta )=\log E[\exp(\theta X)]\,.$

Here $E[\,]$ denotes expectation value with respect to the probability distribution function of $X_{i}$ and $X$ is any one of $X_{i}$s. If $X_{i}$ follows a Gaussian distribution, the rate function becomes a parabola with its apex at the mean of the Gaussian distribution.

If the condition of independent identical distribution is relaxed, particularly if the numbers $X_{i}$ are not independent but nevertheless satisfy the Markov property, the basic large deviations result stated above can be generalized.

Formal definition

Given a Polish space $X$ let $\{\mathbb {P} _{N}\}$ be a sequence of Borel probability measures on $X$, let $\{a_{N}\}$ be a sequence of positive real numbers such that $\lim _{N}a_{N}=+\infty$, and finally let $I:X\to [0,+\infty ]$ be a lower semicontinuous functional on $X$. The sequence $\{\mathbb {P} _{N}\}$ is said to satisfy a large deviation principle with speed $\{a_{n}\}$ and rate $I$, iff for each Borel measurable set $E\subset X$

$-\inf _{x\in E^{\circ }}I(x)\leq \varliminf _{N}a_{N}^{-1}\log {\big (}\mathbb {P} _{N}(E){\big )}\leq \varlimsup _{N}a_{N}^{-1}\log {\big (}\mathbb {P} _{N}(E){\big )}\leq -\inf _{x\in {\bar {E}}}I(x)$

where ${\bar {E}}$ and $E^{\circ }$ denote respectively the closure and interior of $E$.

Brief history

The first rigorous results concerning large deviations are due to the Swedish mathematician Harald Cramér, who applied them to model the insurance business. From the point of view of an insurance company, the earning is at a constant rate per month (the monthly premium) but the claims come randomly. For the company to be successful over a certain period of time (preferably many months), the total earning should exceed the total claim. Thus to estimate the premium you have to ask the following question : "What should we choose as the premium $q$ such that over $N$ months the total claim $C=\Sigma X_{i}$ should be less than $Nq$ ? " This is clearly the same question asked by the large deviations theory. Cramér gave a solution to this question for i.i.d. random variables, where the rate function is expressed as a power series. The results we have quoted above were later obtained by Chernoff, among other people. A very incomplete list of mathematicians who have made important advances would include S.R.S. Varadhan (who has won the Abel prize), D. Ruelle and O.E. Lanford.

Applications

Principles of large deviations may be effectively applied to gather information out of a probabilistic model. Thus, theory of large deviations finds its applications in information theory and risk management. In Physics, the best known application of large deviations theory arise in Thermodynamics and Statistical Mechanics (in connection with relating entropy with rate function).

Large deviations and entropy

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 $M_{N}$ could designate a particular macro-state. And the particular sequence of heads and tails which gives rise to a particular value of $M_{N}$ constitutes a particular micro-state. Loosely speaking a macro-state having more number of micro-states giving rise to it, has higher entropy. And a state with higher entropy has more chance of being realised in actual experiments. The macro-state with mean value of zero (as many heads as tails) has the highest number micro-states giving rise to it and it is indeed the state with the highest entropy. And in most practical situation we shall indeed obtain this macro-state for large number 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 zero is zero. In this way one can see the "rate function" as the negative of the "entropy".

Bibliography

• Special invited paper: Large deviations by S. R. S. Varadhan The Annals of Probability 2008, Vol. 36, No. 2, 397–419 DOI: 10.1214/07-AOP348
• Entropy, Large Deviations and Statistical Mechanics by R.S. Ellis, Springer Publication. ISBN 3-540-29059-1
• Large Deviations for Performance Analysis by Alan Weiss and Adam Shwartz. Chapman and Hall ISBN 0-412-06311-5
• Large Deviations Techniques and Applications by Amir Dembo and Ofer Zeitouni. Springer ISBN 0-387-98406-2
• Random Perturbations of Dynamical Systems by M.I. Freidlin and A.D. Wentzell. Springer ISBN 0-387-98362-7

See also

• Chernoff's inequality
• Contraction principle (large deviations theory), a result on how large deviations principles "push forward"
• Freidlin–Wentzell theorem, a large deviations principle for Itō diffusions
• Laplace principle, a large deviations principle in R^d
• Schilder's theorem, a large deviations principle for Brownian motion
• Varadhan's lemma
• Extreme value theory

External links

• An elementary introduction to the Large Deviations Theory
• Abel Prize 2007 awarded to S.R.S. Varadhan