View source for Large deviations theory

{{Short description|Branch of probability theory}}
{{Use dmy dates|date=August 2020}}
In [[probability theory]], the theory of '''large deviations''' concerns the asymptotic behaviour of remote tails of sequences of probability distributions. While some basic ideas of the theory can be traced to [[Pierre-Simon Laplace|Laplace]], the formalization started with insurance mathematics, namely [[ruin theory]] with [[Harald Cramér|Cramér]] and [[Filip Lundberg|Lundberg]]. A unified formalization of large deviation theory was developed in 1966, in a paper by [[S. R. Srinivasa Varadhan|Varadhan]].<ref>S.R.S. Varadhan, ''Asymptotic probability and differential equations'', [[Communications on Pure and Applied Mathematics|Comm. Pure Appl. Math.]] 19 (1966),261-286.</ref> Large deviations theory formalizes the heuristic ideas of ''concentration of measures'' and widely generalizes the notion of [[Convergence of measures#Weak convergence of random variables|convergence of probability measures]].

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==
{{Quote|text=Any large deviation is done in the least unlikely of all the unlikely ways!|title=Large Deviations|author=Frank den Hollander|source=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 {{nowrap|<math>X_i</math>,}} where we encode head as 1 and tail as 0. Now let <math>M_N</math> denote the mean value after <math>N</math> trials, namely

:{{nowrap|<math>M_N = \frac{1}{N}\sum_{i=1}^{N} X_i</math>.}}

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

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

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

:{{nowrap|<math>I(x) = x\ln{x} + (1-x) \ln(1-x) + \ln{2}</math>.}}

Note that the function <math>I(x)</math> is a convex, nonnegative function that is zero at <math>x = \tfrac{1}{2}</math> and increases as <math>x</math> approaches {{nowrap|<math>1</math>.}} It is the negative of the [[Bernoulli entropy]] with {{nowrap|<math>p = \tfrac{1}{2}</math>;}} 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 {{nowrap|<math>P(M_N > x) < \exp(-NI(x))</math>.}}<ref>"Large deviations for performance analysis: queues, communications, and computing", Shwartz, Adam, 1953- TN: 1228486</ref> This bound is rather sharp, in the sense that <math>I(x)</math> cannot be replaced with a larger number which would yield a strict inequality for all positive {{nowrap|<math>N</math>.}}<ref>Varadhan, S.R.S.,The Annals of Probability 2008, Vol. 36, No. 2, 397–419, [https://math.nyu.edu/faculty/varadhan/wald.pdf]</ref> (However, the exponential bound can still be reduced by a subexponential factor on the order of {{nowrap|<math>1/\sqrt N</math>;}} this follows from the [[Stirling approximation]] applied to the [[binomial coefficient]] appearing in the [[Bernoulli distribution]].) Hence, we obtain the following result:

:{{nowrap|<math>P(M_N > x) \approx \exp(-NI(x))</math>.}}

The probability <math>P(M_N > x)</math> decays exponentially as <math>N \to \infty</math> 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 ===
{{main|Cramér's theorem (large deviations)}}
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 <math>X,X_1,X_2, \ldots</math> be [[i.i.d.|independent and identically distributed]] (i.i.d.) random variables whose common distribution satisfies a certain growth condition. Then the following limit exists:

:{{nowrap|<math>\lim_{N\to \infty} \frac{1}{N} \ln P(M_N > x) = - I(x)</math>.}}

Here

:{{nowrap|<math>M_N = \frac{1}{N}\sum_{i=1}^{N} X_i</math>,}}

as before.

Function <math>I(\cdot)</math> is called the "[[rate function]]" or "Cramér function" or sometimes the "entropy function".

The above-mentioned limit means that for large {{nowrap|<math>N</math>,}}

:{{nowrap|<math>P(M_N >x) \approx \exp[-NI(x) ]</math>,}}

which is the basic result of large deviations theory.<ref>{{Cite web |date=2 February 2012 |title=Large Deviations |url=https://math.nyu.edu/~varadhan/Spring2012/Chapters1-2.pdf |access-date=11 June 2024 |website=www.math.nyu.edu}}</ref><ref>S.R.S. Varadhan, Large Deviations and Applications (SIAM, Philadelphia, 1984)</ref>

If we know the probability distribution of {{nowrap|<math>X</math>,}} an explicit expression for the rate function can be obtained. This is given by a [[Legendre–Fenchel transformation]],<ref>{{cite journal|last=Touchette|first=Hugo|title=The large deviation approach to statistical mechanics|journal=Physics Reports|date=1 July 2009|volume=478|issue=1–3|pages=1–69|doi=10.1016/j.physrep.2009.05.002|arxiv=0804.0327|bibcode=2009PhR...478....1T|s2cid=118416390 }}</ref>

:{{nowrap|<math>I(x) = \sup_{\theta > 0} [\theta x - \lambda(\theta)]</math>,}}

where

:<math>\lambda(\theta) = \ln \operatorname{E}[\exp(\theta X)]</math>

is called the [[cumulant generating function]] (CGF) and <math>\operatorname{E}</math> denotes the [[mathematical expectation]].

If <math>X</math> follows a [[normal distribution]], the rate function becomes a parabola with its apex at the mean of the normal distribution.

If <math>\{X_i\}</math> is an irreducible and aperiodic [[Markov chain]], the variant of the basic large deviations result stated above may hold.{{Citation needed|date=June 2011}}

=== Moderate deviations for sums of independent random variables ===
The previous example controlled the probability of the event <math>[M_N>x]</math>, that is, the concentration of the law of <math>M_N</math> on the [[compact set]] <math>[-x,x]</math>. It is also possible to control the probability of the event <math>[M_N>x a_N]</math> for some sequence <math>a_N\to 0</math>. The following is an example of a '''moderate deviations principle''':<ref>{{Cite book |last1=Dembo |first1=Amir |url=https://books.google.com/books?id=iT9JRlGPx5gC&dq=A.+Dembo+and+O.+Zeitouni.+Large+deviations+techniques+and+applications.+Springer%2C+New+York%2C+%281998%29.&pg=PR7 |title=Large Deviations Techniques and Applications |last2=Zeitouni |first2=Ofer |date=2009-11-03 |publisher=Springer Science & Business Media |isbn=978-3-642-03311-7 |pages=109 |language=en}}</ref><ref>{{Citation |last1=Sethuraman |first1=Jayaram |title=Moderate Deviations |date=2011 |url=http://link.springer.com/10.1007/978-3-642-04898-2_374 |encyclopedia=International Encyclopedia of Statistical Science |pages=847–849 |editor-last=Lovric |editor-first=Miodrag |access-date=2023-07-02 |place=Berlin, Heidelberg |publisher=Springer Berlin Heidelberg |language=en |doi=10.1007/978-3-642-04898-2_374 |isbn=978-3-642-04897-5 |last2=O. |first2=Robert}}</ref>
{{Math theorem
| math_statement = Let <math>X_1,X_2,\dots</math> be a sequence of centered i.i.d variables with finite variance <math>\sigma^2</math> such that <math>\forall \lambda \in \mathbb{R}, \ \ln\mathbb{E}[e^{\lambda X_1}]<\infty </math>. Define <math>M_N:=\frac{1}{N}\sum\limits_{n\leq N} X_N</math>. Then for any sequence <math>1\ll a_N \ll \sqrt{N}</math>:

<math>\lim\limits_{N\to +\infty} \frac{a_N^2}{N} \ln \mathbb{P}[a_N M_N\geq x] = -\frac{x^2}{2\sigma^2}
</math>
}}
In particular, the limit case <math>a_N=\sqrt{N}</math> is the [[central limit theorem]].

==Formal definition==
Given a [[Polish space]] <math>\mathcal{X}</math> let <math>\{\mathbb{P}_N\}</math> be a sequence of [[Borel algebra|Borel]] probability measures on {{nowrap|<math>\mathcal{X}</math>,}} let <math>\{a_N\}</math> be a sequence of positive real numbers such that {{nowrap|<math>\lim_N a_N=\infty</math>,}} and finally let <math>I:\mathcal{X}\to [0, \infty]</math> be a [[lower semicontinuous]] functional on <math>\mathcal{X}.</math> The sequence <math>\{\mathbb{P}_N\}</math> is said to satisfy a '''[[large deviation principle]]''' with ''speed'' <math>\{a_n\}</math> and ''rate'' <math>I</math> if, and only if, for each Borel [[measurable set]] {{nowrap|<math>E \subset \mathcal{X}</math>,}}

:{{nowrap|<math>-\inf_{x \in E^\circ} I(x) \le \varliminf_N a_N^{-1} \log(\mathbb{P}_N(E)) \le \varlimsup_N a_N^{-1} \log(\mathbb{P}_N(E)) \le -\inf_{x \in \overline{E}} I(x)</math>,}}

where <math>\overline{E}</math> and <math>E^\circ</math> denote respectively the [[closure (topology)|closure]] and [[interior (topology)|interior]] of {{nowrap|<math>E</math>.}}{{Citation needed|date=June 2011}}

== 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.<ref>Cramér, H. (1944). On a new limit theorem of the theory of probability. Uspekhi Matematicheskikh Nauk, (10), 166-178.</ref> 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 <math>q</math> such that over <math>N</math> months the total claim <math>C = \Sigma X_i</math> should be less than {{nowrap|<math>Nq</math>?"}} 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 variable]]s, where the rate function is expressed as a [[power series]].

A very incomplete list of mathematicians who have made important advances would include [[Aleksei Zinovyevich Petrov|Petrov]],<ref name="Petrov">Petrov V.V. (1954) Generalization of Cramér's limit theorem. Uspehi Matem. Nauk, v. 9, No 4(62), 195--202.(Russian)</ref> [[Sanov's theorem|Sanov]],<ref name="Sanov">Sanov I.N. (1957) On the probability of large deviations of random magnitudes. Matem. Sbornik, v. 42 (84), 11--44.</ref> [[S.R.S. Varadhan]] (who has won the Abel prize for his contribution to the theory), [[D. Ruelle]], [[Oscar Lanford|O.E. Lanford]], [[Mark Freidlin]], [[Alexander D. Wentzell]], [[Amir Dembo]], and [[Ofer Zeitouni]].<ref>Dembo, A., & Zeitouni, O. (2009). Large deviations techniques and applications (Vol. 38). Springer Science & Business Media</ref>

==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 ===
{{main|asymptotic equipartition property}}
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 <math>M_N</math> could designate a particular macro-state. And the particular sequence of heads and tails which gives rise to a particular value of <math>M_N</math> 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<ref name="Sanov"/> and 
Novak,<ref name="Novak">Novak S.Y. (2011) Extreme value methods with applications to finance. Chapman & Hall/CRC Press. {{isbn|978-1-4398-3574-6}}.</ref> ch. 14.5).

In a special case, large deviations are closely related to the concept of [[Gromov–Hausdorff convergence|Gromov–Hausdorff limits]].<ref>Kotani M., [[Toshikazu Sunada|Sunada T.]] ''Large deviation and the tangent cone at infinity of a crystal lattice'', Math. Z. 254, (2006), 837-870.</ref>

== See also ==
* [[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 "[[Pushforward measure|push forward]]"
* [[Freidlin–Wentzell theorem]], a large deviations principle for [[Itō diffusion]]s
* [[Legendre transformation]], Ensemble equivalence is based on this transformation. 
* [[Laplace principle (large deviations theory)|Laplace principle]], a large deviations principle in '''R'''<sup>''d''</sup>
* [[Laplace's method]]
* [[Schilder's theorem]], a large deviations principle for [[Brownian motion]]
* [[Varadhan's lemma]]
* [[Extreme value theory]]
* [[Large deviations of Gaussian random functions]]

== References ==
{{Reflist}}

==Bibliography==
* [https://arxiv.org/abs/0804.2330v1 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}}
* [https://arxiv.org/abs/1106.4146 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 Hall {{isbn|0-412-06311-5}}
* Large Deviations Techniques and Applications by Amir Dembo and Ofer Zeitouni. Springer {{isbn|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 Society {{isbn|978-0-8218-7578-0}}
* Random Perturbations of Dynamical Systems by [[Mark Freidlin|M.I. Freidlin]] and A.D. Wentzell. Springer {{isbn|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.[http://www.nps.edu/Academics/Schools/GSEAS/SRI/R37.pdf]
*"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.[http://www.nps.edu/Academics/Schools/GSEAS/SRI/R41.pdf]

{{DEFAULTSORT:Large Deviations Theory}}
[[Category:Large deviations theory| ]]
[[Category:Asymptotic analysis]]
[[Category:Asymptotic theory (statistics)]]