Chernoff-Ungleichung

mathematischer Satz

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

Bearbeiten

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

Bearbeiten

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  :
 

Erste Chernoff-Schranke

Bearbeiten

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

Bearbeiten

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

Bearbeiten

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

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

Bearbeiten

Einzelnachweise

Bearbeiten
  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).