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 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 eine Folge von unabhängigen Messungen einer physikalischen Größe, dann ist das arithmetische Mittel 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 . Dies trifft allerdings noch keine Aussage über die Geschwindigkeit der Konvergenz. Das typische Verhalten der Summe wird durch den Grenzwert bestimmt, es ist aber nicht ausgeschlossen, dass sie für ein beliebig großes immer noch stark abweicht, also bspw. 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 eine Folge von unabhängig und identisch verteilten (i.i.d.) reellen Zufallsvariablen, wobei die kumulantenerzeugende Funktion von für jedes endlich sei. Für reelles sei weiter

die Legendre-Transformation von . Der Satz von Cramér besagt nun, dass für alle gilt

Bemerkungen

  • Dass der Limes auf der linken Seite der Gleichung existiert, ist nicht offensichtlich, sondern Teil der Aussage.
  • Die konkrete Wahl der Basis ist nicht essentiell für den Satz. Die kumulantenerzeugende Funktion kann durch für ein beliebiges ersetzt werden, entsprechend betrachtet man dann den Grenzwert des Logarithmus zur Basis .
  • 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 . Die (allgemeine) Chernoff-Ungleichung besagt, dass sogar für jedes endliche gilt .[5]

Satz von Chernoff-Hoeffding

Ein wichtiger Spezialfall des Satzes von Cramér ergibt sich, wenn die Variablen Bernoulli-verteilt sind mit Erwartungswert . Für eine Wahrscheinlichkeit sei

die Kullback-Leibler-Divergenz zwischen Bernoulli-Verteilungen mit Parametern und (in der Einheit Nat). Die kumulantenerzeugende Funktion einer Bernoulli-Variable ist . Daher lässt sich leicht nachweisen, dass die Cramér-Funktion hier gerade die Divergenz ist. Die Summe ist binomialverteilt mit Erwartungswert . Mit Hilfe der Chernoff-Ungleichung ergibt sich nun für

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

Siehe auch

Literatur

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