Hoeffding-Ungleichung - LinkFang.de





Hoeffding-Ungleichung


In der Wahrscheinlichkeitstheorie beschreibt die Hoeffding-Ungleichung (nach Wassilij Hoeffding) die maximale Wahrscheinlichkeit, dass eine Summe von unabhängigen und beschränkten Zufallsvariablen stärker als eine Konstante von ihrem Erwartungswert abweicht.

Die Hoeffding-Ungleichung wird auch die additive Chernoff-Ungleichung genannt und ist ein Spezialfall der Bernstein-Ungleichung.

Satz

Seien [math]X_1, X_2, \ldots, X_n[/math] unabhängige Zufallsvariablen, so dass fast sicher [math]a_i \leq X_i-\textrm{E}[X_i] \leq b_i[/math] gilt. Sei ferner [math]c[/math] eine positive, reellwertige Konstante. Dann gilt:

[math]\Pr\left[\sum (X_i-\textrm{E}[X_i]) \geq c\right] \leq \textrm{exp}\left(\frac{-2c^2}{\sum(b_i-a_i)^2}\right).[/math]

Beweis

Dieser Beweis folgt der Darstellung von D. Pollard, siehe auch Lutz Dümbgens Skriptum (siehe Literatur).

Betrachte zur Vereinfachung der Schreibweise die Zufallsvariablen [math]Y_i = X_i - \textrm{E}[X_i][/math] mit [math]\textrm{E}[Y_i]=0[/math] und ferner für ein zunächst beliebiges [math]z\gt0[/math] die auf den reellen Zahlen monoton wachsende Abbildung [math]x \mapsto \exp(zx)[/math]. Nach der Tschebyschow-Ungleichung gilt dann:

[math] \Pr\left[\sum Y_i \geq c\right] \leq \frac{\textrm{E}[\exp\left(z \sum Y_i\right)]}{\exp(zc)} = \exp(-zc) \cdot \prod \textrm{E}\left[\exp(z Y_i)\right]. [/math]

Wegen der Konvexität der Exponentialfunktion ist

[math] \exp(z Y_i) = \exp\left( \frac{b_i-Y_i}{b_i-a_i}za_i + \frac{Y_i-a_i}{b_i-a_i}zb_i \right) \leq \frac{b_i-Y_i}{b_i-a_i}\exp(za_i) + \frac{Y_i-a_i}{b_i-a_i}\exp(zb_i), [/math]

und mit [math]\textrm{E}[Y_i]=0[/math] folgt, dass

[math] \textrm{E}\left[\exp(z Y_i)\right] \leq \frac{b_i}{b_i-a_i}\exp(za_i) + \frac{-a_i}{b_i-a_i}\exp(zb_i) = e^{-u_i\lambda_i} \left(\left(1-\lambda_i\right)+\lambda_i e^{u_i}\right) [/math]

für die Konstanten [math]\lambda_i = \frac{-a_i}{b_i-a_i}[/math] und [math]u_i = z(b_i-a_i)[/math]. Betrachtet man den Logarithmus der rechten Seite dieses Terms

[math]L(u,\lambda) = -u\lambda + \log\left(\left(1-\lambda\right)+\lambda e^u\right),[/math]

so kann man mittels Kurvendiskussion und Taylor-Reihenentwicklung zeigen, dass stets [math]L(u,\lambda) \leq \frac{u^2}{8}[/math] gilt. Setzt man diesen Wert auf Grund der Monotonie der Exponentialfunktion als obere Schranke in die erste Ungleichung wieder ein, so erhält man

[math] \Pr\left[\sum Y_i \geq c\right] \leq \exp(-zc) \cdot \prod \exp(\frac{u_i^2}{8}) = \exp\left( -zc + \frac{z^2}{8} \sum (b_i-a_i)^2 \right), [/math]

was bei einer Wahl von [math]z=\tfrac{4c}{\sum(b_i-a_i)^2}[/math] zur zu beweisenden Behauptung führt.

Beispiele

  • Betrachte die folgende Frage: Wie wahrscheinlich ist es, bei hundertmaligem Würfeln eine Augensumme von wenigstens 500 zu erreichen? Beschreibt [math]X[/math] das Ergebnis des Würfelwurfs mit [math]\textrm{E}[X] = 3{,}5[/math], also [math]-2{,}5 \leq X-\textrm{E}[X] \leq 2{,}5[/math], so folgt mit der Hoeffding-Ungleichung:
[math] \Pr\left[\sum X \geq 500 \right] = \Pr\left[\sum (X - \textrm{E} [X]) \geq 150 \right] [/math]
[math]\leq \exp\left(\frac{-2 \cdot 150^2}{\sum(2{,}5 + 2{,}5)^2}\right) = \exp\left(\frac{-45000}{100 \cdot 25}\right) = \exp\left(-18\right) \approx 1{,}523 \cdot 10^{-8} [/math]

Literatur

  • Wassily Hoeffding, "Probability Inequalities for Sums of Bounded Random Variables", Journal of the American Statistical Association, Vol. 58, 1963, pp. 13-30.
  • David Pollard, "Convergence of Stochastic Processes", Springer Verlag, 1984.
  • Lutz Dümbgen, Empirische Prozesse, Universität Bern, 2010.
  • Otto Kerner, Joseph Maurer, Jutta Steffens, Thomas Thode und Rudolf Voller, Vieweg Mathematik Lexikon, zweite überarbeitete Auflage, Vieweg Verlag, 1993.

Kategorien: Ungleichung | Stochastik | Satz (Mathematik)

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Hoeffding-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.