Satz von Cramér (Große Abweichungen)

Der Satz von Cramér ist eine Aussage des mathematischen Teilgebiets der Stochastik. Die Arbeit Sur un nouveau théorème-limite de la théorie des probabilités, in der Harald Cramér 1938 seinen Satz veröffentlichte, gilt als die Begründung der Theorie der großen Abweichungen (engl. large deviations theory). Der Satz von Cramér quantifiziert, wie schnell die Wahrscheinlichkeit bestimmter seltener Ereignisse gegen $0$ konvergiert. Die Chernoff-Ungleichung überträgt diese asymptotische Aussage auf den endlichen Fall, in Abgrenzung zu anderen nach Cramér benannten Resultaten spricht man daher auch vom Satz von Cramér-Chernoff.

Einleitendes Beispiel

Sei $X_{1},X_{2},X_{3},...$ eine Folge von unabhängigen Messungen einer physikalischen Größe, dann ist das arithmetische Mittel $\textstyle {\frac {1}{n}}\sum _{i=1}^{n}X_{i}$ ein erwartungstreuer Schätzer für den Erwartungswert. Ist beispielsweise die gesuchte Größe im Einheitsintervall gleichverteilt, so konvergiert nach dem starken Gesetz der großen Zahlen der Mittelwert der Messungen fast sicher gegen $\mathrm {E} [X_{1}]=\mathrm {E} [X_{2}]=\dots =1/2$. Dies trifft allerdings noch keine Aussage über die Geschwindigkeit der Konvergenz. Das typische Verhalten der Summe $\textstyle \sum _{i=1}^{n}X_{i}\approx n/2$ wird durch den Grenzwert bestimmt, es ist aber nicht ausgeschlossen, dass sie für ein beliebig großes $n$ immer noch stark abweicht, also bspw. $\textstyle \sum _{i=1}^{n}X_{i}\geq 2n/3$ gilt. Der Satz von Cramér gibt nun ein allgemeines Verfahren an, wie aus der zugrundeliegenden Verteilung der Größe die Qualität des Schätzers bestimmt werden kann.

Aussage

Sei $(X_{i})_{i\geq 1}$ eine Folge von unabhängig und identisch verteilten (i.i.d.) reellen Zufallsvariablen, wobei die kumulantenerzeugende Funktion $g_{X_{1}}(t)=\ln(\,\mathrm {E} [\mathrm {e} ^{tX_{1}}]\,)$ von $X_{1}$ für jedes $t\in \mathbb {R}$ endlich sei. Für reelles $x$ sei weiter

$\Lambda ^{*}(x)=\sup _{t\in \mathbb {R} }\left(tx-g_{X_{1}}(t)\right)$

die Legendre-Transformation von $g_{X_{1}}$. Der Satz von Cramér besagt nun, dass für alle $x>\mathrm {E} [X_{1}]$ gilt

$\lim _{n\to \infty }\,{\frac {1}{n}}\ln \left(\mathrm {P} \!\left[\sum _{i=1}^{n}X_{i}\geq xn\right]\right)=-\Lambda ^{*}(x).$

Bemerkungen

• Dass der Limes auf der linken Seite der Gleichung existiert, ist nicht offensichtlich, sondern Teil der Aussage.
• Die konkrete Wahl der Basis $\mathrm {e}$ ist nicht essentiell für den Satz. Die kumulantenerzeugende Funktion kann durch $g(t)=\log _{a}(\,\mathrm {E} [a^{tX_{1}}]\,)$ für ein beliebiges $a>0$ ersetzt werden, entsprechend betrachtet man dann den Grenzwert des Logarithmus zur Basis $a$.
• Der Satz von Cramér lässt sich aus dem allgemeinen Fall des Satzes von Sanov herleiten oder alternativ elementar über die exponentielle Tschebyscheff-Ungleichung beweisen.
• Bis auf sublineare additive Terme im Exponenten (d. h. subexponentielle Faktoren) gilt asymptotisch $\textstyle \mathrm {P} [\sum _{i=1}^{n}X_{i}\geq xn]\simeq \mathrm {e} ^{-n\Lambda ^{*}(x)}$. Die (allgemeine) Chernoff-Ungleichung besagt, dass sogar für jedes endliche $n$ gilt $\textstyle \mathrm {P} [\sum _{i=1}^{n}X_{i}\geq xn]\leq \mathrm {e} ^{-n\Lambda ^{*}(x)}$.

Satz von Chernoff-Hoeffding

Ein wichtiger Spezialfall des Satzes von Cramér ergibt sich, wenn die Variablen $X_{i}$ Bernoulli-verteilt sind mit Erwartungswert $\mathrm {E} [X_{1}]=p$. Für eine Wahrscheinlichkeit $0\leq x\leq 1$ sei

$D(x\|p)=x\,\ln \left({\frac {x}{p}}\right)+(1-x)\,\ln \left({\frac {1-x}{1-p}}\right)$

die Kullback-Leibler-Divergenz zwischen Bernoulli-Verteilungen mit Parametern $x$ und $p$ (in der Einheit Nat). Die kumulantenerzeugende Funktion einer Bernoulli-Variable ist $g_{X_{1}}(t)=\ln(p\mathrm {e} ^{t}+1-p)$. Daher lässt sich leicht nachweisen, dass die Cramér-Funktion $\Lambda ^{*}(x)=D(x\|p)$ hier gerade die Divergenz ist. Die Summe $\textstyle X=\sum _{i=1}^{n}X_{i}$ ist binomialverteilt mit Erwartungswert $\mathrm {E} [X]=pn$. Mit Hilfe der Chernoff-Ungleichung ergibt sich nun für $0\leq \varepsilon \leq 1-p$

$\mathrm {P} [X\geq \mathrm {E} [X]+\varepsilon n]\leq \mathrm {e} ^{-nD(p+\varepsilon \|p)}=\left({\frac {p}{p+\varepsilon }}\right)^{(p+\varepsilon )n}\left({\frac {1-p}{1-p-\varepsilon }}\right)^{(1-p-\varepsilon )n}.$

Dies ist der Satz von Chernoff-Hoeffding und wird anschaulich auch als additive Chernoff-Ungleichung bezeichnet.

Siehe auch

• Satz von Sanov
• Hoeffding-Ungleichung

Literatur

• 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. 
• Devdatt P. Dubhashi, Alessandro Panconesi: Concentration of Measure for the Analysis of Randomized Algorithms. Cambridge University Press, New York, NY, USA 2009, ISBN 978-0-521-88427-3.