Inprobability theory, the theory oflarge deviations concerns the asymptotic behaviour of remote tails of sequences of probability distributions. While some basic ideas of the theory can be traced toLaplace, the formalization started with insurance mathematics, namelyruin theory withCramér andLundberg. A unified formalization of large deviation theory was developed in 1966, in a paper byVaradhan.^[1] Large deviations theory formalizes the heuristic ideas ofconcentration of measures and widely generalizes the notion ofconvergence of probability measures.

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

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

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 thelaw 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 thecentral 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, 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 theBernoulli entropy with${\displaystyle p=\frac{1}{2}}$; that it's appropriate for coin tosses follows from theasymptotic equipartition property applied to aBernoulli trial. Then byChernoff's inequality, it can be shown that.^[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 theStirling approximation applied to thebinomial coefficient appearing in theBernoulli 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 onx. 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 anindependent trial, and the probability of getting head or tail is always the same.

Let${\displaystyle X,X_1,X_2,\dots }$ beindependent 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.^[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 aLegendre–Fenchel transformation,^[6]

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

where

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

is called thecumulant generating function (CGF) and${\displaystyle \mathrm{E}}$ denotes themathematical expectation.

If${\displaystyle X}$ follows anormal 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 aperiodicMarkov chain, the variant of the basic large deviations result stated above may hold.^{[citation needed]}

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 thecompact 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 amoderate deviations principle:^[7][8]

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

Given aPolish space${\displaystyle \mathcal{X}}$ let${\displaystyle \{{\mathbb{P}}_N\}}$ be a sequence ofBorel probability measures on${\displaystyle \mathcal{X}}$, let${\displaystyle \{a_N\}}$ be a sequence of positive real numbers such that${\displaystyle \underset{N}{lim}{a}_N=\mathrm{\infty }}$, and finally let${\displaystyle I:\mathcal{X}\to [0,\mathrm{\infty }]}$ be alower semicontinuous functional on${\displaystyle \mathcal{X}.}$ The sequence${\displaystyle \{{\mathbb{P}}_N\}}$ is said to satisfy alarge deviation principle withspeed${\displaystyle \{a_n\}}$ andrate${\displaystyle I}$ if, and only if, for each Borelmeasurable set${\displaystyle E\subset \mathcal{X}}$,

${\displaystyle -\underset{x\in E^{\circ }}{inf}I(x)\le \underset{N}{\underset{\_}{\lim }}{a}_N^{-1}\log ({\mathbb{P}}_N(E))\le \underset{N}{\overline{\lim }}{a}_N^{-1}\log ({\mathbb{P}}_N(E))\le -\underset{x\in \overline{E}}{inf}I(x)}$,

where${\displaystyle \overline{E}}$ and${\displaystyle E^{\circ }}$ denote respectively theclosure andinterior of${\displaystyle E}$.^{[citation needed]}

The first rigorous results concerning large deviations are due to the Swedish mathematicianHarald Cramér, who applied them to model the insurance business.^[9] From the pointof 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${\displaystyle q}$ such that over${\displaystyle N}$ months the total claim${\displaystyle C=\mathrm{\Sigma }{X}_i}$ should be less than${\displaystyle 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 apower series.

A very incomplete list of mathematicians who have made important advances would includePetrov,^[10]Sanov,^[11]S.R.S. Varadhan (who has won the Abel prize for his contribution to the theory),D. Ruelle,O.E. Lanford,Mark Freidlin,Alexander D. Wentzell,Amir Dembo, andOfer Zeitouni.^[12]

Principles of large deviations may be effectively applied to gather information out of a probabilistic model. Thus, theory of large deviations finds its applications ininformation theory andrisk management. In physics, the best known application of large deviations theory arise inthermodynamics andstatistical mechanics (in connection with relatingentropy with rate function).^[13][14]

The rate function is related to theentropy 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 theKullback–Leibler divergence, the connection is established bySanov's theorem (see Sanov^[11] and Novak,^[15] ch. 14.5).

In a special case, large deviations are closely related to the concept ofGromov–Hausdorff limits.^[16]

• Large deviation principle
• Cramér's large deviation theorem
• Chernoff's inequality
• Sanov's theorem
• Contraction principle (large deviations theory), a result on how large deviations principles "push forward"
• Freidlin–Wentzell theorem, a large deviations principle forItō diffusions
• Legendre transformation, Ensemble equivalence is based on this transformation.
• Laplace principle, a large deviations principle inR^d
• Laplace's method
• Schilder's theorem, a large deviations principle forBrownian motion
• Varadhan's lemma
• Extreme value theory
• Large deviations of Gaussian random functions

• Special invited paper: Large deviations by S. R. S. Varadhan The Annals of Probability 2008, Vol. 36, No. 2, 397–419doi:10.1214/07-AOP348
• A basic introduction to large deviations: Theory, applications, simulations, Hugo Touchette, arXiv:1106.4146.
• 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 HallISBN 0-412-06311-5
• Large Deviations Techniques and Applications by Amir Dembo and Ofer Zeitouni. SpringerISBN 0-387-98406-2
• A course on large deviations with an introduction to Gibbs measures by Firas Rassoul-Agha and Timo Seppäläinen. Grad. Stud. Math., 162. American Mathematical SocietyISBN 978-0-8218-7578-0
• Random Perturbations of Dynamical Systems byM.I. Freidlin and A.D. Wentzell. SpringerISBN 0-387-98362-7
• "Large Deviations for Two Dimensional Navier-Stokes Equation with Multiplicative Noise", S. S. Sritharan and P. Sundar, Stochastic Processes and Their Applications, Vol. 116 (2006) 1636–1659.[2]
• "Large Deviations for the Stochastic Shell Model of Turbulence", U. Manna, S. S. Sritharan and P. Sundar, NoDEA Nonlinear Differential Equations Appl. 16 (2009), no. 4, 493–521.[3]

• Large deviations theory
• Asymptotic analysis
• Asymptotic theory (statistics)

• Articles with short description
• Short description matches Wikidata
• Use dmy dates from August 2020
• All articles with unsourced statements
• Articles with unsourced statements from June 2011