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]

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

\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).

Beweis[Bearbeiten]

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

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


\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].

Wegen der Konvexität der Exponentialfunktion ist


\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),

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


\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)

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

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

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


\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),

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

Beispiele[Bearbeiten]

  • Betrachte die folgende Frage: Wie wahrscheinlich ist es, bei hundertmaligem Würfeln eine Augensumme von wenigstens 500 zu erreichen? Beschreibt X das Ergebnis des Würfelwurfs mit \textrm{E}[X] = 3{,}5, also -2{,}5 \leq X-\textrm{E}[X] \leq 2{,}5, so folgt mit der Hoeffding-Ungleichung:

\Pr\left[\sum X \geq 500 \right]
= \Pr\left[\sum (X - \textrm{E} [X]) \geq 150 \right]
\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}

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.