Hoeffding-Ungleichung

mathematischer Satz

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.

Seien   stochastisch unabhängige Zufallsvariablen, so dass fast sicher   gilt. Sei ferner   eine positive, reellwertige Konstante. Dann gilt:

 

Dieser 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

Bearbeiten

Betrachtet 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.