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

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