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).^[1][2] Der Satz von Cramér quantifiziert, wie schnell die Wahrscheinlichkeit bestimmter seltener Ereignisse gegen ${\displaystyle 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.^[3]

Einleitendes Beispiel

Sei ${\displaystyle X_{1},X_{2},X_{3},...}$ eine Folge von unabhängigen Messungen einer physikalischen Größe, dann ist das arithmetische Mittel ${\displaystyle \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 ${\displaystyle \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 ${\displaystyle \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 ${\displaystyle n}$ immer noch stark abweicht, also bspw. ${\displaystyle \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 ${\displaystyle (X_{i})_{i\geq 1}}$ eine Folge von unabhängig und identisch verteilten (i.i.d.) reellen Zufallsvariablen, wobei die kumulantenerzeugende Funktion ${\displaystyle g_{X_{1}}(t)=\ln(\,\mathrm {E} [\mathrm {e} ^{tX_{1}}]\,)}$ von ${\displaystyle X_{1}}$ für jedes ${\displaystyle t\in \mathbb {R} }$ endlich sei. Für reelles ${\displaystyle x}$ sei weiter

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

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

${\displaystyle \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 ${\displaystyle \mathrm {e} }$ ist nicht essentiell für den Satz. Die kumulantenerzeugende Funktion kann durch ${\displaystyle g(t)=\log _{a}(\,\mathrm {E} [a^{tX_{1}}]\,)}$ für ein beliebiges ${\displaystyle a>0}$ ersetzt werden, entsprechend betrachtet man dann den Grenzwert des Logarithmus zur Basis ${\displaystyle 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.^[4]
• Bis auf sublineare additive Terme im Exponenten (d. h. subexponentielle Faktoren) gilt asymptotisch ${\displaystyle \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 ${\displaystyle n}$ gilt ${\displaystyle \textstyle \mathrm {P} [\sum _{i=1}^{n}X_{i}\geq xn]\leq \mathrm {e} ^{-n\Lambda ^{*}(x)}}$.^[5]

Satz von Chernoff-Hoeffding

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

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

${\displaystyle \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.^[6][7]

Siehe auch

• Hoeffding-Ungleichung
• Satz von Sanov

Literatur

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

Einzelnachweise

1. ↑ Harald Cramér: Sur un nouveau théorème-limite de la théorie des probabilités. Colloque consacré à la théorie des probabilités. In: Actualités scientifiques et industrielles. Band 736, 1938, S. 2–23. 
2. ↑ Hugo Touchette: Large Deviation Theory: History, Sources, References, and Pointers. Division of Applied Mathematics, Stellenbosch University, Stellenbosch, South Africa; abgerufen am 4. März 2020 .
3. ↑ Norbert Straumann: Statistische Mechanik: Einführung und Weiterführendes. Springer, Berlin & Heidelberg, Deutschland 2017, ISBN 978-3-662-52950-8, S. 10, doi:10.1007/978-3-662-52950-8. 
4. ↑ Matthias Löwe: Große Abweichungen. (PDF; 418 kB) Westfälische Wilhelms-Universität Münster, Institut für Mathematische Stochastik; abgerufen am 8. März 2020 .
5. ↑ Thomas M. Cover, Joy A. Thomas: Elements of Information Theory. 2. Auflage. John Wiley & Sons, Hoboken, NJ, USA 2006, S. 392 f. 
6. ↑ Wassily Hoeffding: Probability Inequalities for Sums of Bounded Random Variables. In: Journal of the American Statistical Association. Band 58, 1984, S. 13–30, doi:10.2307/2282952. 
7. ↑ 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.