Chernoff-Ungleichung

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

In der Wahrscheinlichkeitstheorie beschreibt die nach Herman Chernoff benannte, jedoch auf Herman Rubin zurückgehende[1] [2] Chernoff-Ungleichung eine obere Schranke für die Wahrscheinlichkeit, dass eine Sequenz unabhängiger Bernoulli-Experimente von ihrer erwarteten Anzahl an Erfolgen abweicht.

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

Satz[Bearbeiten | Quelltext 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:

Beweis der ersten Chernoff-Schranke[Bearbeiten | Quelltext 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.

Beweis der zweiten Chernoff-Schranke[Bearbeiten | Quelltext bearbeiten]

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

Varianten[Bearbeiten | Quelltext 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.

Beispiele[Bearbeiten | Quelltext 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 | Quelltext bearbeiten]

Einzelnachweise[Bearbeiten | Quelltext bearbeiten]

  1. Herman Chernoff A career in statistics. In: Past, Present, and Future of Statistics.. CRC Press, 2014, ISBN 9781482204964.
  2. John Bather: A Conversation with Herman Chernoff. In: Statistical Science. 11, Nr. 4, November 1996, S. 335-350. doi:10.1214/ss/1032280306.