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},\ldots ,X_{n}$ stochastisch 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 _{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).$

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}-{\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(zY_{i})\right].$

Wegen der Konvexität der Exponentialfunktion ist

$\exp(zY_{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(zY_{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 {\biggl (}{\frac {u_{i}^{2}}{8}}{\biggr )}=\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.

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},\ldots ,X_{n}$ stochastisch unabhängige und identisch verteilte Zufallsvariablen mit der Verteilung $\Pr(X_{1}=k)={\frac {1}{6}}$ für $k=1,\ldots 6$ sind. Dabei gilt ${\textrm {E}}[X_{1}]=3{,}5$. Für die Berechnung der gesuchten Wahrscheinlichkeit $\Pr(S\geq 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:

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

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

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.