Hoeffding-Ungleichung

In d​er Wahrscheinlichkeitstheorie beschreibt d​ie Hoeffding-Ungleichung (nach Wassilij Hoeffding) d​ie maximale Wahrscheinlichkeit, d​ass eine Summe v​on unabhängigen u​nd beschränkten Zufallsvariablen stärker a​ls eine Konstante v​on ihrem Erwartungswert abweicht.

Die Hoeffding-Ungleichung w​ird auch d​ie additive Chernoff-Ungleichung genannt u​nd ist e​in Spezialfall d​er Bernstein-Ungleichung.

Satz

Seien ${\displaystyle X_{1},X_{2},\ldots ,X_{n}}$ unabhängige Zufallsvariablen, so dass fast sicher ${\displaystyle a_{i}\leq X_{i}-{\textrm {E}}[X_{i}]\leq b_{i}}$ gilt. Sei ferner ${\displaystyle c}$ eine positive, reellwertige Konstante. Dann gilt:

${\displaystyle \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 f​olgt der Darstellung v​on D. Pollard, s​iehe auch Lutz Dümbgens Skriptum (siehe Literatur).

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

${\displaystyle \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 d​er Konvexität d​er Exponentialfunktion ist

${\displaystyle \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 ${\displaystyle {\textrm {E}}[Y_{i}]=0}$ folgt, dass

${\displaystyle {\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 ${\displaystyle \lambda _{i}={\frac {-a_{i}}{b_{i}-a_{i}}}}$ und ${\displaystyle u_{i}=z(b_{i}-a_{i})}$. Betrachtet man den Logarithmus der rechten Seite dieses Terms

${\displaystyle 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 ${\displaystyle 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

${\displaystyle \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 ${\displaystyle 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 ${\displaystyle X}$ das Ergebnis des Würfelwurfs mit ${\displaystyle {\textrm {E}}[X]=3{,}5}$, also ${\displaystyle -2{,}5\leq X-{\textrm {E}}[X]\leq 2{,}5}$, so folgt mit der Hoeffding-Ungleichung:

${\displaystyle \Pr \left[\sum X\geq 500\right]=\Pr \left[\sum (X-{\textrm {E}}[X])\geq 150\right]}$

${\displaystyle \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.