Large deviations theory

{{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}}

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|$X\_i$,}} where we encode head as 1 and tail as 0. Now let $M\_N$ denote the mean value after $N$ trials, namely

:{{nowrap|$M\_N\; =\; \backslash frac\{1\}\{N\}\backslash sum\_\{i=1\}^\{N\}\; X\_i$.}}

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

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

Let us make this statement more precise. For a given value {{nowrap|

:{{nowrap|$I(x)\; =\; x\backslash ln\{x\}\; +\; (1-x)\; \backslash ln(1-x)\; +\; \backslash ln\{2\}$.}}

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

:{{nowrap|$P(M\_N\; >\; x)\; \backslash approx\; \backslash exp(-NI(x))$.}}

The probability $P(M\_N\; >\; x)$ decays exponentially as $N\; \backslash to\; \backslash 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.

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

:{{nowrap|$\backslash lim\_\{N\backslash to\; \backslash infty\}\; \backslash frac\{1\}\{N\}\; \backslash ln\; P(M\_N\; >\; x)\; =\; -\; I(x)$.}}

Here

:{{nowrap|$M\_N\; =\; \backslash frac\{1\}\{N\}\backslash sum\_\{i=1\}^\{N\}\; X\_i$,}}

as before.

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

The above-mentioned limit means that for large {{nowrap|$N$,}}

:{{nowrap|$P(M\_N\; >x)\; \backslash approx\; \backslash exp[-NI(x)\; ]$,}}

which is the basic result of large deviations theory.{{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}}S.R.S. Varadhan, Large Deviations and Applications (SIAM, Philadelphia, 1984)

If we know the probability distribution of {{nowrap|$X$,}} an explicit expression for the rate function can be obtained. This is given by a Legendre–Fenchel transformation,{{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 }}

:{{nowrap|$I(x)\; =\; \backslash sup\_\{\backslash theta\; >\; 0\}\; [\backslash theta\; x\; -\; \backslash lambda(\backslash theta)]$,}}

where

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

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

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

If $\backslash \{X\_i\backslash \}$ is an irreducible and aperiodic Markov chain, the variant of the basic large deviations result stated above may hold.{{Citation needed|date=June 2011}}

The previous example controlled the probability of the event $[M\_N>x]$, that is, the concentration of the law of $M\_N$ on the compact set $[-x,x]$. It is also possible to control the probability of the event $[M\_N>x\; a\_N]$ for some sequence $a\_N\backslash to\; 0$. The following is an example of a moderate deviations principle:{{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}}{{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}}

{{Math theorem

| math_statement = Let $X\_1,X\_2,\backslash dots$ be a sequence of centered i.i.d variables with finite variance $\backslash sigma^2$ such that . Define $M\_N:=\backslash frac\{1\}\{N\}\backslash sum\backslash limits\_\{n\backslash leq\; N\}\; X\_N$. Then for any sequence $1\backslash ll\; a\_N\; \backslash ll\; \backslash sqrt\{N\}$:

$\backslash lim\backslash limits\_\{N\backslash to\; +\backslash infty\}\; \backslash frac\{a\_N^2\}\{N\}\; \backslash ln\; \backslash mathbb\{P\}[a\_N\; M\_N\backslash geq\; x]\; =\; -\backslash frac\{x^2\}\{2\backslash sigma^2\}$

}}

In particular, the limit case $a\_N=\backslash sqrt\{N\}$ is the central limit theorem.

Given a Polish space $\backslash mathcal\{X\}$ let $\backslash \{\backslash mathbb\{P\}\_N\backslash \}$ be a sequence of Borel probability measures on {{nowrap|$\backslash mathcal\{X\}$,}} let $\backslash \{a\_N\backslash \}$ be a sequence of positive real numbers such that {{nowrap|$\backslash lim\_N\; a\_N=\backslash infty$,}} and finally let $I:\backslash mathcal\{X\}\backslash to\; [0,\; \backslash infty]$ be a lower semicontinuous functional on $\backslash mathcal\{X\}.$ The sequence $\backslash \{\backslash mathbb\{P\}\_N\backslash \}$ is said to satisfy a large deviation principle with speed $\backslash \{a\_n\backslash \}$ and rate $I$ if, and only if, for each Borel measurable set {{nowrap|$E\; \backslash subset\; \backslash mathcal\{X\}$,}}

:{{nowrap|$-\backslash inf\_\{x\; \backslash in\; E^\backslash circ\}\; I(x)\; \backslash le\; \backslash varliminf\_N\; a\_N^\{-1\}\; \backslash log(\backslash mathbb\{P\}\_N(E))\; \backslash le\; \backslash varlimsup\_N\; a\_N^\{-1\}\; \backslash log(\backslash mathbb\{P\}\_N(E))\; \backslash le\; -\backslash inf\_\{x\; \backslash in\; \backslash overline\{E\}\}\; I(x)$,}}

where $\backslash overline\{E\}$ and $E^\backslash circ$ denote respectively the closure and interior of {{nowrap|$E$.}}{{Citation needed|date=June 2011}}

The first rigorous results concerning large deviations are due to the Swedish mathematician Harald Cramér, who applied them to model the insurance business.Cramér, H. (1944). On a new limit theorem of the theory of probability. Uspekhi Matematicheskikh Nauk, (10), 166-178. 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\; =\; \backslash Sigma\; X\_i$ should be less than {{nowrap|$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.

A very incomplete list of mathematicians who have made important advances would include Petrov,Petrov V.V. (1954) Generalization of Cramér's limit theorem. Uspehi Matem. Nauk, v. 9, No 4(62), 195--202.(Russian) Sanov,Sanov I.N. (1957) On the probability of large deviations of random magnitudes. Matem. Sbornik, v. 42 (84), 11--44. 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, and Ofer Zeitouni.Dembo, A., & Zeitouni, O. (2009). Large deviations techniques and applications (Vol. 38). Springer Science & Business Media

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).

{{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 $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 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 and

Novak,Novak S.Y. (2011) Extreme value methods with applications to finance. Chapman & Hall/CRC Press. {{isbn|978-1-4398-3574-6}}. ch. 14.5).

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

• 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 for Itō diffusions
• Legendre transformation, Ensemble equivalence is based on this transformation.
• Laplace principle, a large deviations principle in R^d
• 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

{{Reflist}}

• [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 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:Asymptotic analysis

Category:Asymptotic theory (statistics)