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 $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

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 − E[X_i] mit 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 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

• 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 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

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