Large deviations theory

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 Laplace, the formalization started with insurance mathematics, namely ruin theory with Cramér and Lundberg. A unified formalization of large deviation theory was developed in 1966, in a paper by Varadhan.^[1] 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 decline of the probability measures of certain kinds of extreme or tail 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 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}}$ – 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 \operatorname {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 \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}}$.

Man beachte, dass die Funktion eine konvexe, nichtnegative Funktion ist, die bei null ist und mit zunehmendem wächst . Sie ist das Negative der Bernoulli-Entropie mit ; ​​dass sie für Münzwürfe geeignet ist, folgt aus der asymptotischen Gleichverteilungseigenschaft, angewendet auf einen Bernoulli-Versuch . Dann lässt sich mithilfe der Chernoff-Ungleichung zeigen, dass . ^{[ 2 ]} Diese Schranke ist ziemlich scharf, da nicht durch eine größere Zahl ersetzt werden kann, was eine strikte Ungleichung für alle positiven zur Folge hätte . ^{[ 3 ]} (Die exponentielle Schranke kann jedoch noch um einen subexponentiellen Faktor in der Größenordnung von reduziert werden ; dies folgt aus der Stirling-Approximation, angewendet auf den Binomialkoeffizienten in der Bernoulli-Verteilung .) Daher erhalten wir das folgende Ergebnis: ${\displaystyle I(x)}$${\displaystyle x={\tfrac {1}{2}}}$${\displaystyle x}$${\displaystyle 1}$${\displaystyle p={\tfrac {1}{2}}}$${\displaystyle P(M_{N}>x)<\exp(-NI(x))}$${\displaystyle I(x)}$${\displaystyle N}$${\displaystyle 1/{\sqrt {N}}}$

${\displaystyle P(M_{N}>x)\approx \exp(-NI(x))}$Die

Die Wahrscheinlichkeit nimmt exponentiell mit einer von x abhängigen Rate ab . Diese Formel approximiert jede Randwahrscheinlichkeit des Stichprobenmittelwerts von unabhängigen und identisch verteilten Zufallsvariablen und gibt deren Konvergenz bei zunehmender Anzahl von Stichproben an. ${\displaystyle P(M_{N}>x)}$${\displaystyle N\to \infty }$

Im obigen Beispiel des Münzwurfs haben wir ausdrücklich angenommen, dass jeder Wurf ein unabhängiger Versuch ist und die Wahrscheinlichkeit, Kopf oder Zahl zu erhalten, immer gleich ist.

Seien unabhängige und identisch verteilte (iid) Zufallsvariablen , deren gemeinsame Verteilung eine bestimmte Wachstumsbedingung erfüllt. Dann existiert der folgende Grenzwert: ${\displaystyle X,X_{1},X_{2},\ldots }$

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

Hier

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

wie zuvor.

Diese Funktion wird als „ Ratenfunktion “ oder „Cramér-Funktion“ oder manchmal auch als „Entropiefunktion“ bezeichnet. ${\displaystyle I(\cdot )}$

Die oben genannte Grenze bedeutet, dass für große Werte von ,${\displaystyle N}$

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

Dies ist das grundlegende Ergebnis der Theorie großer Abweichungen. ^{[ 4 ] [ 5 ]}

Kennt man die Wahrscheinlichkeitsverteilung von , so lässt sich ein expliziter Ausdruck für die Ratenfunktion herleiten. Dieser wird durch eine Legendre-Fenchel-Transformation gegeben ^{[ 6 ].}${\displaystyle X}$

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

Wo

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

wird als kumulantenerzeugende Funktion (CGF) bezeichnet und steht für den mathematischen Erwartungswert . ${\displaystyle \operatorname {E} }$

Wenn die Funktion einer Normalverteilung folgt , wird die Ratenfunktion zu einer Parabel, deren Scheitelpunkt im Mittelwert der Normalverteilung liegt. ${\displaystyle X}$

Falls es sich um eine irreduzible und aperiodische Markov-Kette handelt , kann die oben genannte Variante des grundlegenden Ergebnisses für große Abweichungen gelten. ${\displaystyle \{X_{i}\}}$

Im vorherigen Beispiel wurde die Wahrscheinlichkeit des Ereignisses kontrolliert , d. h. die Konzentration des Gesetzes auf der kompakten Menge . Es ist auch möglich, die Wahrscheinlichkeit des Ereignisses für eine bestimmte Folge zu kontrollieren . Im Folgenden ein Beispiel für ein Prinzip moderater Abweichungen : ^{[ 7 ] [ 8 ]}${\displaystyle [M_{N}>x]}$${\displaystyle M_{N}}$${\displaystyle [-x,x]}$${\displaystyle [M_{N}>xa_{N}]}$${\displaystyle a_{N}\to 0}$

Insbesondere handelt es sich im Grenzfall um den zentralen Grenzwertsatz . ${\displaystyle a_{N}={\sqrt {N}}}$

Gegeben sei ein polnischer Raum. Sei eine Folge von Borel- Wahrscheinlichkeitsmaßen auf , sei eine Folge positiver reeller Zahlen mit , und sei schließlich ein unterhalbstetiges Funktional auf . Die Folge erfüllt ein Prinzip großer Abweichungen mit Geschwindigkeit und Rate genau dann, wenn für jede Borel- messbare Menge gilt :${\displaystyle {\mathcal {X}}}$${\displaystyle \{\mathbb {P} _{N}\}}$${\displaystyle {\mathcal {X}}}$${\displaystyle \{a_{N}\}}$${\displaystyle \lim _{N}a_{N}=\infty }$${\displaystyle I:{\mathcal {X}}\to [0,\infty ]}$${\displaystyle {\mathcal {X}}.}$${\displaystyle \{\mathbb {P} _{N}\}}$${\displaystyle \{a_{n}\}}$${\displaystyle I}$${\displaystyle E\subset {\mathcal {X}}}$

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

wobei und jeweils den Abschluss und das Innere von bezeichnen .${\displaystyle {\overline {E}}}$${\displaystyle E^{\circ }}$${\displaystyle E}$

Die ersten strengen Ergebnisse zu großen Abweichungen stammen von dem schwedischen Mathematiker Harald Cramér , der sie zur Modellierung des Versicherungsgeschäfts anwandte. ^{[ 9 ]} Aus Sicht eines Versicherungsunternehmens sind die Einnahmen monatlich konstant (die monatliche Prämie), während die Schadensfälle zufällig auftreten. Damit das Unternehmen über einen bestimmten Zeitraum (vorzugsweise mehrere Monate) erfolgreich ist, müssen die Gesamteinnahmen die Gesamtschadensfälle übersteigen. Um die Prämie zu schätzen, muss man sich daher folgende Frage stellen: „Welche Prämie sollten wir wählen, damit die Gesamtschadensfälle über Monate hinweg kleiner als … sind ?“ Dies ist im Wesentlichen die Fragestellung der Theorie der großen Abweichungen. Cramér lieferte eine Lösung für unabhängige und identisch verteilte Zufallsvariablen , deren Ratenfunktion als Potenzreihe ausgedrückt wird . ${\displaystyle q}$${\displaystyle N}$${\displaystyle C=\Sigma X_{i}}$${\displaystyle Nq}$

Eine sehr unvollständige Liste von Mathematikern, die wichtige Fortschritte erzielt haben, würde Petrov , ^{[ 10 ]} Sanov , ^{[ 11 ]} SRS Varadhan (der für seinen Beitrag zur Theorie den Abelpreis gewonnen hat), D. Ruelle , OE Lanford , Mark Freidlin , Alexander D. Wentzell , Amir Dembo und Ofer Zeitouni umfassen . ^{[ 12 ]}

Die Prinzipien großer Abweichungen lassen sich effektiv anwenden, um aus einem probabilistischen Modell Informationen zu gewinnen. Daher findet die Theorie großer Abweichungen Anwendung in der Informationstheorie und im Risikomanagement . In der Physik ist die bekannteste Anwendung der Theorie großer Abweichungen in der Thermodynamik und der statistischen Mechanik zu finden (im Zusammenhang mit der Beziehung zwischen Entropie und Ratenfunktion). ^{[ 13 ] [ 14 ]}

Die Ratenfunktion steht in Zusammenhang mit der Entropie in der statistischen Mechanik. Dies lässt sich folgendermaßen veranschaulichen: In der statistischen Mechanik hängt die Entropie eines bestimmten Makrozustands von der Anzahl der zugehörigen Mikrozustände ab. In unserem Beispiel mit dem Münzwurf könnte der Mittelwert einen bestimmten Makrozustand darstellen. Die spezifische Abfolge von Kopf und Zahl, die zu einem bestimmten Wert führt, bildet einen bestimmten Mikrozustand. Vereinfacht gesagt, besitzt ein Makrozustand mit einer höheren Anzahl an Mikrozuständen, die zu ihm führen, eine höhere Entropie. Ein Zustand mit höherer Entropie tritt in Experimenten mit höherer Wahrscheinlichkeit auf. Der Makrozustand mit dem Mittelwert 1/2 (gleich viele Kopf- wie Zahlwürfe) hat die meisten zugehörigen Mikrozustände und weist daher die höchste Entropie auf. In den meisten praktischen Situationen werden wir diesen Makrozustand auch nach einer großen Anzahl von Versuchen erreichen. Die „Ratenfunktion“ misst hingegen die Wahrscheinlichkeit des Auftretens eines bestimmten Makrozustands. Je kleiner die Ratenfunktion, desto höher ist die Wahrscheinlichkeit für das Auftreten eines Makrozustands. Bei unserem Münzwurf ist der Wert der „Ratenfunktion“ bei einem Mittelwert von 1/2 gleich null. Somit kann man die „Ratenfunktion“ als das Negative der „Entropie“ betrachten. ${\displaystyle M_{N}}$${\displaystyle M_{N}}$

Zwischen der „Ratenfunktion“ in der Theorie großer Abweichungen und der Kullback-Leibler-Divergenz besteht ein Zusammenhang; dieser Zusammenhang wird durch den Satz von Sanov hergestellt (siehe Sanov ^{[ 11 ]} und Novak, ^{[ 15 ]} Kap. 14.5).

In einem Sonderfall stehen große Abweichungen in engem Zusammenhang mit dem Konzept der Gromov-Hausdorff-Grenzwerte . ^{[ 16 ]}

• Prinzip der großen Abweichung
• Cramérs Satz der großen Abweichungen
• Chernoffs Ungleichheit
• Satz von Sanov
• Kontraktionsprinzip (Theorie der großen Abweichungen) , ein Ergebnis darüber, wie Prinzipien großer Abweichungen " vorwärts drängen ".
• Satz von Freidlin-Wentzell , ein Prinzip großer Abweichungen für Itō-Diffusionen
• Legendre-Transformation ; Ensemble-Äquivalenz basiert auf dieser Transformation.
• Laplace-Prinzip , ein Prinzip großer Abweichungen in R ^d
• Laplace-Methode
• Schilders Theorem , ein Prinzip großer Abweichungen für die Brownsche Bewegung
• Varadhans Lemma
• Extremwerttheorie
• Große Abweichungen von Gaußschen Zufallsfunktionen

• Eingeladener Sonderbeitrag: Große Abweichungen von SRS Varadhan. The Annals of Probability 2008, Band 36, Nr. 2, 397–419. doi : 10.1214/07-AOP348
• Eine grundlegende Einführung in große Abweichungen: Theorie, Anwendungen, Simulationen , Hugo Touchette, arXiv:1106.4146.
• Entropie, große Abweichungen und statistische Mechanik von R. S. Ellis, Springer-Verlag. ISBN 3-540-29059-1
• Große Abweichungen für die Leistungsanalyse von Alan Weiss und Adam Shwartz. Chapman and Hall ISBN 0-412-06311-5
• Techniken und Anwendungen zur Berechnung großer Abweichungen von Amir Dembo und Ofer Zeitouni. Springer ISBN 0-387-98406-2
• Ein Kurs über große Abweichungen mit einer Einführung in Gibbs-Maße von Firas Rassoul-Agha und Timo Seppäläinen. Grad. Stud. Math., 162. American Mathematical Society ISBN 978-0-8218-7578-0
• Zufällige Störungen dynamischer Systeme von M. I. Freidlin und A. D. Wentzell. Springer ISBN 0-387-98362-7
• „Große Abweichungen für die zweidimensionale Navier-Stokes-Gleichung mit multiplikativem Rauschen“, SS Sritharan und P. Sundar, Stochastic Processes and Their Applications, Band 116 (2006) 1636–1659. [2]
• „Große Abweichungen für das stochastische Schalenmodell der Turbulenz“, U. Manna, SS Sritharan und P. Sundar, NoDEA Nonlinear Differential Equations Appl. 16 (2009), Nr. 4, 493–521. [3]