Chernoff-Ungleichung

In der Wahrscheinlichkeitstheorie beschreibt der Begriff Chernoff-Ungleichung eine obere Schranke für die Wahrscheinlichkeit, dass eine Sequenz unabhängiger Zufallsvariablen von ihrer erwarteten Anzahl an Erfolgen abweicht. Die Ungleichung wurde nach Herman Chernoff benannt, geht jedoch auf Herman Rubin zurück.[1][2]

Die Chernoff-Ungleichung ist ein vielseitiges und vielfach verwendetes Hilfsmittel bei der Analyse von randomisierten Algorithmen in der Informatik.

Allgemeine Formulierung

Die allgemeinste Form der Chernoff-Ungleichung für eine Zufallsvariable erhält man durch Anwenden der Markov-Ungleichung auf :

Für alle gilt

und somit auch

Diese Form der Chernoff-Ungleichung verwendet die momenterzeugende Funktion von . Für eine gegebene Verteilung von kann durch Ausrechnen dieser Funktion eine spezifische Chernoff-Ungleichung errechnet werden.

Chernoff-Ungleichung für Binomialverteilungen

Sei eine Sequenz von unabhängigen Bernoulli-Experimenten mit und . Demnach beschreibt die erwartete Anzahl an Erfolgen () des Experiments.

1. Dann gilt für jedes
2. Für jedes gilt:
3. Für alle :

Beweis

Erste Chernoff-Schranke

Sei eine zunächst beliebige Konstante. Bezeichne im Folgenden zur Vereinfachung der Schreibweise eine neue Zufallsvariable vermöge . Auf Grund der Monotonie der Abbildung folgt dann

,

wobei als definiert ist und die letzte Abschätzung mittels Markow-Ungleichung folgt. Nun gilt

und somit

.

Damit folgt

.

Betrachte nun . Dann gilt

.

Für einen Teil des Exponenten des rechten Terms

kann man mittels Kurvendiskussion und Taylor-Reihenentwicklung zeigen, dass stets gilt. Auf Grund der Monotonie der Exponentialfunktion gilt

.

Zusammen mit der ersten Abschätzung folgt die Behauptung.

Zweite Chernoff-Schranke

Der Beweis der zweiten Schranke folgt technisch analog zur ersten Schranke.


Dritte Chernoff-Schranke

Die Beweisidee besteht darin die Markow-Ungleichung auf anzuwenden, wobei .

Dann gilt aufgrund der Unabhängigkeit der Bernoulli-Experimente:

Was abgeschätzt werden kann durch:

Durch die Zusatzbedingung, dass , folgt:

Also gilt:

Chernoff-Ungleichung mithilfe der Standardabweichung

Eine allgemeine Variante der Chernoff-Ungleichung lässt sich mittels der Standardabweichung formulieren. Seien diskrete, unabhängige Zufallsvariablen mit und . Bezeichne die Varianz von . Dann gilt für jedes :

.

Der Beweis ist technisch analog zu dem oben gezeigten Beweis.

Beispiele

  • Betrachte die folgende Frage: Wie wahrscheinlich ist es, beim zehnmaligen Wurf einer fairen Münze wenigstens siebenmal das Ergebnis „Zahl“ zu erhalten? Die Münzwürfe stellen Bernoulli-Experimente mit dar. Somit folgt nach der ersten Chernoff-Ungleichung:
  • Man formuliere das obige Beispiel nur leicht um und frage stattdessen: Wie wahrscheinlich ist es, bei hundertmaligem fairen Münzwurf wenigstens siebzigmal das Ergebnis „Zahl“ zu erhalten? Sofort erweist sich die erste Chernoff-Schranke als deutlich stärker:

Literatur

Einzelnachweise

  1. John Bather: A Conversation with Herman Chernoff. In: Statistical Science. 11. Jahrgang, Nr. 4, November 1996, S. 335–350, doi:10.1214/ss/1032280306.
  2. Herman Chernoff: A career in statistics. In: Xihong Lin, Christian Genest, David L. Banks, Geert Molenberghs, David W. Scott, Jane-Ling Wang (Hrsg.): Past, Present, and Future of Statistics. CRC Press, 2014, ISBN 978-1-4822-0496-4, S. 35 (crcpress.com).