Hoeffding-Ungleichung
In der Wahrscheinlichkeitstheorie beschreibt die Hoeffding-Ungleichung (nach Wassilij Hoeffding) eine obere Schranke für die maximale Wahrscheinlichkeit, dass eine Summe von stochastisch 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
BearbeitenSeien stochastisch unabhängige Zufallsvariablen, so dass fast sicher gilt. Sei ferner eine positive, reellwertige Konstante. Dann gilt:
Beweis
BearbeitenDieser Beweis folgt der Darstellung von D. Pollard, siehe auch Lutz Dümbgens Skriptum (siehe Literatur).
Betrachte zur Vereinfachung der Schreibweise die Zufallsvariablen mit und ferner für ein zunächst beliebiges die auf den reellen Zahlen monoton wachsende Abbildung . Nach der Tschebyschow-Ungleichung gilt dann:
Wegen der Konvexität der Exponentialfunktion ist
und mit folgt, dass
für die Konstanten und . Betrachtet man den Logarithmus der rechten Seite dieses Terms
so kann man mittels Kurvendiskussion und Taylor-Reihenentwicklung zeigen, dass stets gilt. Setzt man diesen Wert auf Grund der Monotonie der Exponentialfunktion als obere Schranke in die erste Ungleichung wieder ein, so erhält man
was bei einer Wahl von zur zu beweisenden Behauptung führt.
Beispiel
BearbeitenBetrachtet wird die Fragestellung: Wie wahrscheinlich ist es, bei hundertmaligem Würfeln eine Augensumme von wenigstens 500 zu erreichen?
- Diese Frage kann exakt mit Hilfe der Verteilung der Summenvariablen beantwortet werden, wobei stochastisch unabhängige und identisch verteilte Zufallsvariablen mit der Verteilung für sind. Dabei gilt . Für die Berechnung der gesuchten Wahrscheinlichkeit ergibt sich ein gewisser Aufwand durch kombinatorische und numerische Probleme, weswegen auch Approximationen oder Abschätzungen mit Hilfe einer Ungleichung von Interesse sein können.
- Eine approximative Lösung erhält man beispielsweise, indem man die Wahrscheinlichkeitsverteilung der Zufallsvariablen durch eine Normalverteilung mit demselben Erwartungswert und derselben Varianz approximiert. Die Verteilung der Zufallsvariablen ist in diesem Fall aufgrund des zentralen Grenzwertsatzes gut durch eine Normalverteilung approximierbar.
- Häufig genügt für viele Anwendungen bei kleinen Wahrscheinlichkeiten die Angabe einer Oberschranke für die gesuchte Wahrscheinlichkeit. Im Beispiel ergibt sich mit der Hoeffding-Ungleichung:
- Somit ist eine Oberschranke für die mit der Frage gesuchte Wahrscheinlichkeit, die erheblich kleiner als die angegebene Oberschranke sein kann.
Literatur
Bearbeiten- 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.