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 ${\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.

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.
• 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)}}$.

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.

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. 

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.