Chernoff-Ungleichung - LinkFang.de





Chernoff-Ungleichung


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

Sei [math]X_1, X_2, \ldots, X_n[/math] eine Sequenz von [math]n[/math] unabhängigen Bernoulli-Experimenten mit [math]P[X_i=1] = p[/math] und [math]P[X_i=0] = 1-p[/math]. Demnach beschreibt [math]pn[/math] die erwartete Anzahl an Erfolgen ([math]X_i=1[/math]) des Experiments.

1. Dann gilt für jedes [math]\delta\gt0[/math]
[math] P\left[ \sum X_i \geq (1+\delta)\cdot pn \right] \leq \exp\left( -\frac{\min\{\delta,\delta^2\}}{3}pn \right) [/math]
2. Für jedes [math]\delta \in [0,1][/math] gilt:
[math] P\left[ \sum X_i \leq (1-\delta)\cdot pn \right] \leq \exp\left( -\frac{\delta^2}{2}pn \right) [/math]

Beweis der ersten Chernoff-Schranke

Sei [math]t \gt 0[/math] eine zunächst beliebige Konstante. Bezeichne [math]Y[/math] im Folgenden zur Vereinfachung der Schreibweise eine neue Zufallsvariable vermöge [math]Y = \exp\left( t \sum X_i \right)[/math]. Auf Grund der Monotonie der Abbildung [math]x \mapsto \exp(tx)[/math] folgt dann

[math] P\left[ \sum X_i \geq (1+\delta)\cdot pn \right] = P\left[Y \geq \exp\left(t(1+\delta)\cdot pn\right) \right] = P\left[Y \geq k \textrm{E}\left[Y\right] \right] \leq \frac{1}{k} [/math],

wobei [math]k[/math] als [math]k = \frac{\exp(t(1+\delta)pn)}{\textrm{E}[Y]}[/math] definiert ist und die letzte Abschätzung mittels Markow-Ungleichung folgt. Nun gilt

[math] \textrm{E}\left[ \exp(tX_i) \right] = (1-p) e^0 + p e^t = 1 + (e^t-1)p [/math]

und somit

[math] \textrm{E}\left[ Y \right] = \textrm{E}\left[ \exp(t\sum X_i) \right] = \textrm{E}\left[ \prod \exp(tX_i) \right] = \prod \textrm{E}\left[ \exp(tX_i) \right] = \left(1 + (e^t-1)p\right)^n [/math].

Damit folgt

[math] \frac{1}{k} = e^{-t(1+\delta)pn} \left(1 + (e^t-1)p\right)^n \leq e^{-t(1+\delta)pn} \cdot e^{(e^t-1)pn} = e^{-t(1+\delta)pn + (e^t-1)pn} [/math].

Betrachte nun [math]t = \log(1+\delta)[/math]. Dann gilt

[math] \frac{1}{k} \leq e^{-(\log(1+\delta))(1+\delta)pn + \delta pn} = e^{( \delta-(1+\delta)\log(1+\delta) ) pn} [/math].

Für einen Teil des Exponenten des rechten Terms

[math] L(\delta) = (1+\delta) \log(1+\delta) [/math]

kann man mittels Kurvendiskussion und Taylor-Reihenentwicklung zeigen, dass stets [math]L(\delta) \geq \delta+\frac{1}{3}\min\{\delta,\delta^2\}[/math] gilt. Auf Grund der Monotonie der Exponentialfunktion gilt:[math] \frac{1}{k} \leq e^{( \delta- (\delta+\frac{1}{3}\min\{\delta,\delta^2\}) ) pn} = \exp\left( -\frac{\min\{\delta,\delta^2\}}{3}pn \right) [/math]. Zusammen mit der ersten Abschätzung folgt die Behauptung.

Beweis der zweiten Chernoff-Schranke

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

Varianten

  • Eine allgemeine Variante der Chernoff-Ungleichung lässt sich mittels der Standardabweichung formulieren. Seien [math]X_1, X_2, \ldots, X_n[/math] diskrete, unabhängige Zufallsvariablen mit [math]\textrm{E}[X_i] = 0[/math] und [math]|X_i| \leq 1[/math]. Bezeichne [math]\sigma^2[/math] die Varianz von [math]X = \sum X_i[/math]. Dann gilt für jedes [math]0 \lt \lambda \leq 2\sigma[/math]:
[math]P\left[\left|\sum X_i\right| \geq \lambda\sigma\right] \leq 2 \exp\left(-\frac{\lambda^2}{4}\right)[/math]
Der Beweis ist technisch analog zu dem oben gezeigten.

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 [math]X_1,X_2,\ldots,X_{10}[/math] mit [math]pn = \frac{1}{2} \cdot 10 = 5[/math] dar. Somit folgt nach der ersten Chernoff-Ungleichung:
[math] P\left[ \sum X_i \geq 7 \right] = P\left[ \sum X_i \geq \left(1+\frac{4}{10}\right)\cdot 5 \right] [/math]
[math] \leq \exp\left( -\frac{\min\{\frac{4}{10},\frac{16}{100}\}}{3} \cdot 5 \right) = \exp\left(-\frac{4}{15}\right) \approx 0{,}766\ldots [/math]
  • 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:
[math] P\left[ \sum X_i \geq 70 \right] = P\left[ \sum X_i \geq \left(1+\frac{4}{10}\right)\cdot 50 \right] [/math]
[math] \leq \exp\left( -\frac{\min\{\frac{4}{10},\frac{16}{100}\}}{3} \cdot 50 \right) = \exp\left(-\frac{8}{3}\right) \approx 0{,}069\ldots [/math]

Literatur

Einzelnachweise

  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 .

Kategorien: Ungleichung | Stochastik | Satz (Mathematik)

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Chernoff-Ungleichung (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.