Hoeffding-Ungleichung

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

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.

Inhaltsverzeichnis

Satz[Bearbeiten | Quelltext bearbeiten]

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

Beweis[Bearbeiten | Quelltext bearbeiten]

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.

Beispiele[Bearbeiten | Quelltext bearbeiten]

  • Betrachte die folgende Frage: Wie wahrscheinlich ist es, bei hundertmaligem Würfeln eine Augensumme von wenigstens 500 zu erreichen? Beschreibt das Ergebnis des Würfelwurfs mit , also , so folgt mit der Hoeffding-Ungleichung:

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