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 ist eng mit der Informationstheorie verbunden. Der Satz formalisiert die Intuition, dass die Gesamtwahrscheinlichkeit eines seltenen Ereignisses von der Wahrscheinlichkeit des plausibelsten Teilereignisses dominiert wird. Er ist nach dem russischen Mathematiker Ivan Nikolajewitsch Sanov (1919–1968) benannt.

Einleitendes Beispiel

Sei $X_1,X_2,X_3,\dots$ eine Folge von fairen Münzwürfen, modelliert als i.i.d. Bernoulli-Variablen mit Erfolgswahrscheinlichkeit $1/2,$ also $X_1\sim \mathrm{Ber}(1/2)$. „Kopf“ entspreche dabei der $1$, „Zahl“ der $0$. Das starke Gesetz der großen Zahlen besagt, dass das arithmetische Mittel

$S_n=\frac{1}{n}\sum _{i=1}^n{X}_i$

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

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

${\hat{P}}_n=\frac{1}{n}\sum _{i=1}^n{\delta }_{X_i}$

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

Endlicher Fall

Sei $𝒳$ eine endliche Menge und $𝒫$ die Menge aller Wahrscheinlichkeitsmaße auf $𝒳$ versehen mit der schwachen Topologie (vgl. Konvergenz in Verteilung). Sei weiter $(X_i{)}_{i\ge 1}$ eine Folge von i.i.d. Zufallsvariablen, wobei $X_1\sim P$ gemäß einem festen $P\in 𝒫$ verteilt sei, und sei ${\hat{P}}_n$ die empirische Verteilung von $X_1,\dots ,X_n$. Für ein Wahrscheinlichkeitsmaß $Q\in 𝒫$ bezeichne schließlich $D(Q\Vert P)=\sum _{x\in 𝒳}Q(x)\cdot \log \frac{Q(x)}{P(x)}$ die Kullback-Leibler-Divergenz von $P$ zu $Q$.

Unter diesen Voraussetzungen besagt der Satz von Sanov, dass für jede Menge $\mathrm{\Gamma }\subseteq 𝒫$ gilt:

$-\underset{Q\in \mathrm{int}(\mathrm{\Gamma })}{\inf }D(Q\Vert P)\le \underset{n\to \mathrm{\infty }}{\mathrm{lim\; inf}}\frac{1}{n}\log (\mathrm{P}[{\hat{P}}_n\in \mathrm{\Gamma }])\le \underset{n\to \mathrm{\infty }}{\mathrm{lim\; sup}}\frac{1}{n}\log (\mathrm{P}[{\hat{P}}_n\in \mathrm{\Gamma }])\le -\underset{Q\in \mathrm{cl}(\mathrm{\Gamma })}{\inf }D(Q\Vert P)$

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

$\underset{n\to \mathrm{\infty }}{\lim }\frac{1}{n}\log (\mathrm{P}[{\hat{P}}_n\in \mathrm{\Gamma }])=-\underset{Q\in \mathrm{\Gamma }}{\inf }D(Q\Vert 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 $𝒳$ und der Stetigkeit von $D(\cdot \Vert P)$ folgt $\underset{Q\in \mathrm{cl}(\mathrm{\Gamma })}{\inf }D(Q\Vert P)=\underset{Q\in \mathrm{\Gamma }}{\inf }D(Q\Vert P)$, das Infimum über das Innere von $\mathrm{\Gamma }$ kann aber echt größer sein.
• Falls $\mathrm{\Gamma }$ konvex ist, dann ist das Maß $P^{*}={\arg \min }_{Q\in \mathrm{\Gamma }}D(Q\Vert P)$ wohldefiniert und wird die Informationsprojektion (engl. information projection) von $P$ auf $\mathrm{\Gamma }$ genannt.
• Bis auf sublineare additive Terme im Exponenten (d. h. subexponentielle Faktoren) gilt asymptotisch $\mathrm{P}[{\hat{P}}_n\in \mathrm{\Gamma }]\simeq {\mathrm{e}}^{-n\inf D(Q\Vert P)}$, wenn die Divergenz in Nat angegeben ist. Es lässt sich sogar zeigen: Für jedes $n$ gilt $\mathrm{P}[{\hat{P}}_n\in \mathrm{\Gamma }]\le (n+1{)}^{|𝒳|}\cdot {\mathrm{e}}^{-n\inf D(Q\Vert P)}.$
• Das empirische Maß ${\hat{P}}_n$ kann nicht beliebige Werte annehmen, sondern liegt stets in ${𝒫}_n=\{Q\in 𝒫|\mathrm{\forall }x\in 𝒳:nQ(x)\in \{0,1,\dots ,n\}\}$, die Elemente von ${𝒫}_n$ werden Typen genannt. Die Wahrscheinlichkeit, dass ${\hat{P}}_n$ ein konkreter Typ $Q\in {𝒫}_n$ ist, lässt sich durch $(n+1{)}^{-|𝒳|}{\mathrm{e}}^{-nD(Q\Vert P)}\le \mathrm{P}[{\hat{P}}_n=Q]\le {\mathrm{e}}^{-nD(Q\Vert P)}$ abschätzen.

Insgesamt wird also die Wahrscheinlichkeit $\mathrm{P}[{\hat{P}}_n\in \mathrm{\Gamma }]$ von demjenigen Typ $Q\in \mathrm{\Gamma }$ dominiert, der die kleinste Divergenz von der „wahren“ Verteilung $P$ hat. Jeder andere Typ $Q^{\prime }$ mit $D(Q^{\prime }\Vert P)\ge D(Q\Vert P)+\epsilon$ hat eine exponentiell kleinere Wahrscheinlichkeit.

Allgemeiner Fall

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

Mit diesen angepassten Voraussetzungen besagt der Satz von Sanov erneut, dass für jede Menge $\mathrm{\Gamma }\subseteq 𝒫$ gilt:

$-\underset{Q\in \mathrm{int}(\mathrm{\Gamma })}{\inf }D(Q\Vert P)\le \underset{n\to \mathrm{\infty }}{\mathrm{lim\; inf}}\frac{1}{n}\log (\mathrm{P}[{\hat{P}}_n\in \mathrm{\Gamma }])\le \underset{n\to \mathrm{\infty }}{\mathrm{lim\; sup}}\frac{1}{n}\log (\mathrm{P}[{\hat{P}}_n\in \mathrm{\Gamma }])\le -\underset{Q\in \mathrm{cl}(\mathrm{\Gamma })}{\inf }D(Q\Vert P)$

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

$\underset{n\to \mathrm{\infty }}{\lim }\frac{1}{n}\log (\mathrm{P}[{\hat{P}}_n\in \mathrm{\Gamma }])=-\underset{Q\in \mathrm{\Gamma }}{\inf }D(Q\Vert P)$

Literatur

• Vorlage:Literatur
• Vorlage:Literatur
• Vorlage:Literatur