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

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

<math>\Pr\left[\sum_{i=1}^n (X_i-\textrm{E}[X_i]) \geq c\right] \leq \textrm{exp}\left(\frac{-2c^2}{\sum_{i=1}^n(b_i-a_i)^2}\right).</math>

Beweis

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

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

<math>

\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]. </math> Wegen der Konvexität der Exponentialfunktion ist

<math>

\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), </math> und mit <math>\textrm{E}[Y_i]=0</math> folgt, dass

<math>

\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) </math> für die Konstanten <math>\lambda_i = \frac{-a_i}{b_i-a_i}</math> und <math>u_i = z(b_i-a_i)</math>. Betrachtet man den Logarithmus der rechten Seite dieses Terms

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

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

<math>

\Pr\left[\sum Y_i \geq c\right] \leq \exp(-zc) \cdot \prod \exp\biggl(\frac{u_i^2}{8}\biggr) = \exp\left( -zc + \frac{z^2}{8} \sum (b_i-a_i)^2 \right), </math> was bei einer Wahl von <math>z=\tfrac{4c}{\sum(b_i-a_i)^2}</math> zur zu beweisenden Behauptung führt.

Beispiel

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 <math>S = \sum_{i=1}^{100} X_i</math> beantwortet werden, wobei <math>X_1,\ldots,X_n</math> stochastisch unabhängige und identisch verteilte Zufallsvariablen mit der Verteilung <math>\Pr(X_1=k) = \frac{1}{6}</math> für <math>k=1,\ldots 6</math> sind. Dabei gilt <math>\textrm{E}[X_1] = 3{,}5</math>. Für die Berechnung der gesuchten Wahrscheinlichkeit <math>\Pr(S \geq 500)</math> 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 <math>S</math> durch eine Normalverteilung mit demselben Erwartungswert und derselben Varianz approximiert. Die Verteilung der Zufallsvariablen <math>S</math> 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:

<math>

\Pr[S \geq 500] = \Pr\left[\sum_{i=1}^{100}X_i - 350 \geq 150\right] = \Pr\left[\sum_{i=1}^{100} (X_i - 3{,}5) \geq 150\right] = \Pr\left[\sum_{i=1}^{100} (X_i - \textrm{E}[X_i]) \geq 150 \right] </math>

<math>\leq \exp\left(\frac{-2 \cdot 150^2}{\sum_{i=1}^{100}(2{,}5 + 2{,}5)^2}\right)

= \exp\left(\frac{-45000}{100 \cdot 25}\right)

= \exp\left(-18\right)

\approx 1{,}523 \cdot 10^{-8} </math>

Somit ist <math>e^{-18}</math> eine Oberschranke für die mit der Frage gesuchte Wahrscheinlichkeit, die erheblich kleiner als die angegebene Oberschranke sein kann.

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.