Satz von Sanov

Der Satz von Sanov ist ein Resultat des mathematischen Teilgebiets der Stochastik. Er ist eine zentrale Aussage der Theorie der großen Abweichungen (engl. large deviations theory) und zeigt eine enge Verbindung zur Informationstheorie auf. Der Satz formalisiert die Intuition, dass die Gesamtwahrscheinlichkeit eines seltenen Ereignisses von der Wahrscheinlichkeit des plausibelsten Teilereignisses dominiert wird.[1] Er ist nach dem russischen Mathematiker Ivan Nikolajewitsch Sanov (1919–1968) benannt.[2]

Einleitendes Beispiel

Sei ${\displaystyle X_{1},X_{2},X_{3},\dots }$ eine Folge von fairen Münzwürfen, modelliert als unabhängig und identisch verteilte (i.i.d.) Bernoulli-Variablen mit Erfolgswahrscheinlichkeit ${\displaystyle 1/2}$, also ${\displaystyle X_{1}\sim \operatorname {Ber} (1/2)}$. "Kopf" entspreche dabei der ${\displaystyle 1}$, "Zahl" der ${\displaystyle 0}$. Das starke Gesetz der großen Zahlen besagt, dass das arithmetische Mittel

${\displaystyle S_{n}={\frac {1}{n}}\sum _{i=1}^{n}X_{i}}$

fast sicher gegen den Erwartungswert ${\displaystyle \mathrm {E} [X_{1}]=\mathrm {E} [X_{2}]=\dots =1/2}$ konvergiert. Es trifft aber keine Aussage über die Geschwindigkeit der Konvergenz. Typischerweise wird der Mittelwert nahe bei ${\displaystyle 1/2}$ sein, es ist aber nicht ausgeschlossen, dass er für ein beliebig großes ${\displaystyle n}$ immer noch stark vom Grenzwert abweicht, also bspw. ${\displaystyle S_{n}\geq 2/3}$ gilt. Der Satz von Sanov quantifiziert wie schnell die Wahrscheinlichkeit einer solchen Abweichung gegen ${\displaystyle 0}$ geht. Über das asymptotische Verhalten hinaus kann man sich auch fragen, wie wahrscheinlich der Mittelwert für ein konkretes ${\displaystyle n}$ abweicht. In seinem berühmten Werk The Doctrine of Chances behandelte Abraham de Moivre beispielsweise ein Gedankenexperiment von ${\displaystyle 3600}$ Münzwürfen. Wie hoch ist die Wahrscheinlichkeit für ${\displaystyle S_{3600}\geq 2/3}$?

Solche Fragen lassen sich wie folgt maßtheoretisch formalisieren: Sei ${\displaystyle {\mathcal {P}}}$ die Menge aller Wahrscheinlichkeitsmaße auf ${\displaystyle \{0,1\}}$, also die Gesamtheit aller Bernoulli-Verteilungen. Für jede positive ganze Zahl ${\displaystyle n}$ sei

${\displaystyle {\hat {P}}_{n}={\frac {1}{n}}\sum _{i=1}^{n}\delta _{X_{i}}}$

die empirische Verteilung der ersten ${\displaystyle n}$ Münzwürfe, wobei ${\displaystyle \delta _{x}}$ das Dirac-Maß an der Stelle ${\displaystyle x}$ bezeichne. Es gilt dann stets ${\displaystyle {\hat {P}}_{n}\in {\mathcal {P}}}$ und nach dem Gesetz der großen Zahlen konvergiert ${\displaystyle {\hat {P}}_{n}\,{\xrightarrow {\text{ f.s. }}}\,\operatorname {Ber} (1/2)}$. Außerdem sei ${\displaystyle \textstyle \Gamma =\{\mathrm {Ber} (p)\,|\,p\geq 2/3\}\subseteq {\mathcal {P}}}$ die Teilmenge aller Verteilungen mit Erwartungswert mindestens ${\displaystyle 2/3}$. Dann ist die Wahrscheinlichkeit ${\displaystyle \mathrm {P} [{\hat {P}}_{n}\in \Gamma ]}$, dass das zufällige Maß ${\displaystyle {\hat {P}}_{n}}$ in ${\displaystyle \Gamma }$ liegt, genau die Wahrscheinlichkeit ${\displaystyle \mathrm {P} [S_{n}\geq 2/3]}$.

Endlicher Fall

Sei ${\displaystyle {\mathcal {X}}}$ eine endliche Menge und ${\displaystyle {\mathcal {P}}}$ die Menge aller Wahrscheinlichkeitsmaße auf ${\displaystyle {\mathcal {X}}}$ versehen mit der schwachen Topologie (vgl. Konvergenz in Verteilung). Sei weiter ${\displaystyle (X_{i})_{i\geq 1}}$ eine Folge von i.i.d. Zufallsvariablen, wobei ${\displaystyle X_{1}\sim P}$ gemäß einem festen ${\displaystyle P\in {\mathcal {P}}}$ verteilt sei, und sei ${\displaystyle {\hat {P}}_{n}}$ die empirische Verteilung von ${\displaystyle X_{1},\dots ,X_{n}}$. Für ein Wahrscheinlichkeitsmaß ${\displaystyle Q\in {\mathcal {P}}}$ bezeichne schließlich ${\displaystyle \textstyle D(Q\|P)=\sum _{x\in {\mathcal {X}}}Q(x)\cdot \log {Q(x) \over P(x)}}$ die Kullback-Leibler-Divergenz von ${\displaystyle P}$ zu ${\displaystyle Q}$.

Unter diesen Voraussetzungen besagt der Satz von Sanov, dass für jede Menge ${\displaystyle \Gamma \subseteq {\mathcal {P}}}$ gilt[3][4]

${\displaystyle -\inf _{Q\in \operatorname {int} (\Gamma )}\,D(Q\|P)\leq \liminf _{n\to \infty }\,{\frac {1}{n}}\log \left(\,\mathrm {P} [{\hat {P}}_{n}\in \Gamma ]\,\right)\leq \limsup _{n\to \infty }\,{\frac {1}{n}}\log \left(\,\mathrm {P} [{\hat {P}}_{n}\in \Gamma ]\,\right)\leq -\inf _{Q\in \operatorname {cl} (\Gamma )}\,D(Q\|P).}$

Hierbei ist ${\displaystyle \operatorname {int} (\Gamma )}$ das Innere und ${\displaystyle \operatorname {cl} (\Gamma )}$ der Abschluss von ${\displaystyle \Gamma }$. Falls außerdem die linke und die rechte Seite der Ungleichungskette übereinstimmen, dann existiert der Grenzwert und es gilt

${\displaystyle \lim _{n\to \infty }\,{\frac {1}{n}}\log \left(\,\mathrm {P} [{\hat {P}}_{n}\in \Gamma ]\,\right)=-\inf _{Q\in \Gamma }\,D(Q\|P).}$

Bemerkungen

• Die konkrete Wahl der Basis des Logarithmus ist unerheblich, es muss aber darauf geachtet werden, dass dieselbe wie bei der Divergenz verwendet wird (vgl. Shannon (Einheit)).
• Aus der Endlichkeit von ${\displaystyle {\mathcal {X}}}$ und der Stetigkeit von ${\displaystyle D(\,\cdot \,\|P)}$ folgt ${\displaystyle \textstyle \,\inf _{Q\in \operatorname {cl} (\Gamma )}\,D(Q\|P)=\inf _{Q\in \Gamma }\,D(Q\|P)}$, das Infimum über das Innere von ${\displaystyle \Gamma }$ kann aber echt größer sein.
• Falls ${\displaystyle \Gamma }$ konvex ist, dann ist das Maß ${\displaystyle \textstyle P^{*}={\arg \min }_{Q\in \Gamma }\,D(Q\|P)}$ wohldefiniert und wird die Informationsprojektion (engl. information projection) von ${\displaystyle P}$ auf ${\displaystyle \Gamma }$ genannt.[5]
• Bis auf sublineare additive Terme im Exponenten (d. h. subexponentielle Faktoren) gilt asymptotisch ${\displaystyle \mathrm {P} [{\hat {P}}_{n}\in \Gamma ]\simeq \mathrm {e} ^{-n\inf D(Q\|P)}}$, wenn die Divergenz in Nat angeben ist. Es lässt sich sogar zeigen, dass für jedes ${\displaystyle n}$ gilt ${\displaystyle \mathrm {P} [{\hat {P}}_{n}\in \Gamma ]\leq (n+1)^{|{\mathcal {X}}|}\cdot \mathrm {e} ^{-n\inf D(Q\|P)}.}$[4]
• Das empirische Maß ${\displaystyle {\hat {P}}_{n}}$ kann nicht beliebige Werte annehmen, sondern liegt stets in ${\displaystyle \textstyle {\mathcal {P}}_{n}=\{Q\in {\mathcal {P}}\,|\,\forall x\in {\mathcal {X}}\colon \,nQ(x)\in \{0,1,\dots ,n\}\}}$, die Elemente von ${\displaystyle {\mathcal {P}}_{n}}$ werden Typen genannt. Die Wahrscheinlichkeit, dass ${\displaystyle {\hat {P}}_{n}}$ ein konkreter Typ ${\displaystyle Q\in {\mathcal {P}}_{n}}$ ist, lässt sich durch ${\displaystyle (n+1)^{-|{\mathcal {X}}|}\mathrm {e} ^{-nD(Q\|P)}\leq \mathrm {P} [{\hat {P}}_{n}=Q]\leq \mathrm {e} ^{-nD(Q\|P)}}$ abschätzen.[4]

Insgesamt wird also die Wahrscheinlichkeit ${\displaystyle \mathrm {P} [{\hat {P}}_{n}\in \Gamma ]}$ von demjenigen Typ ${\displaystyle Q\in \Gamma }$ dominiert, der die kleinste Divergenz von der "wahren" Verteilung ${\displaystyle P}$ hat. Jeder andere Typ ${\displaystyle Q'}$ mit ${\displaystyle D(Q'\|P)\geq D(Q\|P)+\varepsilon }$ hat eine exponentiell kleinere Wahrscheinlichkeit.

Allgemeiner Fall

Der Satz von Sanov lässt sich erheblich verallgemeinern, insbesondere die Endlichkeit der Grundmenge ist unnötig. Sei nun ${\displaystyle {\mathcal {X}}}$ ein beliebiger polnischer Raum (bspw. der ${\displaystyle \mathbb {R} ^{d}}$), ${\displaystyle {\mathcal {P}}}$ die Menge aller Wahrscheinlichkeitsmaße auf ${\displaystyle {\mathcal {X}}}$ mit der schwachen Topologie und wieder ${\displaystyle (X_{i})_{i\geq 1}}$ eine Folge von i.i.d. ${\displaystyle {\mathcal {X}}}$-wertigen Zufallsvariablen mit ${\displaystyle X_{1}\sim P}$ für ein ${\displaystyle P\in {\mathcal {P}}}$. Jedes absolut stetige Maß ${\displaystyle Q\ll P}$ besitzt eine Radon-Nikodým-Dichte ${\displaystyle \textstyle f}$ bezüglich ${\displaystyle P}$, die Divergenz ist dann durch ${\displaystyle \textstyle D(Q\|P)=\int f\log f\,\mathrm {d} P}$ erklärt, für alle übrigen Maße kann man gefahrlos ${\displaystyle D(Q\|P)=+\infty }$ setzen. Beachte, dass die empirischen Maße ${\displaystyle {\hat {P}}_{n}\ll P}$ offensichtlich immer absolut stetig bezüglich ${\displaystyle P}$ sind.

Mit diesen angepassten Voraussetzungen besagt der Satz von Sanov erneut, dass für jede Menge ${\displaystyle \Gamma \subseteq {\mathcal {P}}}$ gilt[1][3]

${\displaystyle -\inf _{Q\in \operatorname {int} (\Gamma )}\,D(Q\|P)\leq \liminf _{n\to \infty }\,{\frac {1}{n}}\log \left(\,\mathrm {P} [{\hat {P}}_{n}\in \Gamma ]\,\right)\leq \limsup _{n\to \infty }\,{\frac {1}{n}}\log \left(\,\mathrm {P} [{\hat {P}}_{n}\in \Gamma ]\,\right)\leq -\inf _{Q\in \operatorname {cl} (\Gamma )}\,D(Q\|P).}$

Falls ${\displaystyle \Gamma =\operatorname {cl} (\operatorname {int} (\Gamma ))}$ der Abschluss seines Inneren ist, dann gilt

${\displaystyle \lim _{n\to \infty }\,{\frac {1}{n}}\log \left(\,\mathrm {P} [{\hat {P}}_{n}\in \Gamma ]\,\right)=-\inf _{Q\in \Gamma }\,D(Q\|P).}$

Literatur

• Thomas M. Cover, Joy A. Thomas: Elements of Information Theory. 2. Auflage. John Wiley & Sons, Hoboken, NJ, USA 2006.
• Amir Dembo, Ofer Zeitouni: Large Deviations Techniques and Applications (= Stochastic Modelling and Applied Probability. Nr. 38). 2. Auflage. Springer, Berlin & Heidelberg, Deutschland 2010, doi:10.1007/978-3-642-03311-7.
• Jean-Dominique Deuschel, Daniel W. Stroock: Large Deviations (= Pure and Applied Mathematics. Nr. 137). Academic Press, Boston, MA, USA 1989, doi:10.1016/S0079-8169(08)61645-1.

Einzelnachweise

1. Ramon van Handel: Stochastic Analysis Seminar - Lecture 3. Sanov’s Theorem. Princeton University, Princeton, NJ, USA, 10. Oktober 2013.
2. Hugo Touchette: Large Deviation Theory: History, Sources, References, and Pointers. Division of Applied Mathematics, Stellenbosch University, Stellenbosch, South Africa
3. Ivan N. Sanov: On the Probability of Large Deviations of Random Variables. In: North Carolina State University, Departement of Statistics (Hrsg.): Institute of Statistics Mimeo Series. Nr. 192, 1958 (englisch, ncsu.edu – russisch: О вероятности больших отклонений случайных величин. 1957. Übersetzt von Dana E.A. Quade).
4. Thomas M. Cover, Joy A. Thomas: Elements of Information Theory. 2. Auflage. John Wiley & Sons, Hoboken, NJ, USA 2006, S. 362 f.
5. Imre Csiszár, František Matúš: Information Projections Revisited. In: IEEE Transaction on Information Theory. Band 49, Nr. 6, 2003, S. 1474–1490, doi:10.1109/TIT.2003.810633.