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 $X_1,X_2,\dots ,X_n$ stochastisch unabhängige Zufallsvariablen, so dass fast sicher $a_i\le X_i-\text{E}[X_i]\le b_i$ gilt. Sei ferner $c$ eine positive, reellwertige Konstante. Dann gilt:

$\mathrm{Pr}[\sum _{i=1}^n(X_i-\text{E}[X_i])\ge c]\le \text{exp}\left(\frac{-2c^2}{\sum _{i=1}^n(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-\text{E}[X_i]$ mit $\text{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:

$\mathrm{Pr}[\sum Y_i\ge c]\le \frac{\text{E}[\exp (z\sum Y_i)]}{\exp (zc)}=\exp (-zc)\cdot \prod \text{E}[\exp (z{Y}_i)].$

Wegen der Konvexität der Exponentialfunktion ist

$\exp (z{Y}_i)=\exp (\frac{b_i-Y_i}{b_i-a_i}z{a}_i+\frac{Y_i-a_i}{b_i-a_i}z{b}_i)\le \frac{b_i-Y_i}{b_i-a_i}\exp (z{a}_i)+\frac{Y_i-a_i}{b_i-a_i}\exp (z{b}_i),$

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

$\text{E}[\exp (z{Y}_i)]\le \frac{b_i}{b_i-a_i}\exp (z{a}_i)+\frac{-a_i}{b_i-a_i}\exp (z{b}_i)=e^{-u_i{\lambda }_i}((1-{\lambda }_i)+{\lambda }_i{e}^{u_i})$

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 ((1-\lambda )+\lambda e^u),$

so kann man mittels Kurvendiskussion und Taylor-Reihenentwicklung zeigen, dass stets $L(u,\lambda )\le \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

$\mathrm{Pr}[\sum Y_i\ge c]\le \exp (-zc)\cdot \prod \exp \left(\frac{u_i^2}{8}\right)=\exp (-zc+\frac{z^2}{8}\sum (b_i-a_i{)}^2),$

was bei einer Wahl von $z=\frac{4c}{\sum (b_i-a_i{)}^2}$ 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 $S=\sum _{i{=}^1}^{100}{X}_i$ beantwortet werden, wobei $X_1,\dots ,X_n$ stochastisch unabhängige und identisch verteilte Zufallsvariablen mit der Verteilung $\mathrm{Pr}(X_1=k)=\frac{1}{6}$ für $k=1,\dots 6$ sind. Dabei gilt $\text{E}[X_1]=3,5$. Für die Berechnung der gesuchten Wahrscheinlichkeit $\mathrm{Pr}(S\ge 500)$ 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 $S$ durch eine Normalverteilung mit demselben Erwartungswert und derselben Varianz approximiert. Die Verteilung der Zufallsvariablen $S$ 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:

$\mathrm{Pr}[S\ge 500]=\mathrm{Pr}[\sum _{i=1}^{100}{X}_i-350\ge 150]=\mathrm{Pr}[\sum _{i=1}^{100}(X_i-3,5)\ge 150]=\mathrm{Pr}[\sum _{i=1}^{100}(X_i-\text{E}[X_i])\ge 150]$

$\le \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 (-18)\approx 1,523\cdot 10^{-8}$

Somit ist $e^{-18}$ 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.