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 ${\displaystyle X_{1},X_{2},\ldots ,X_{n}}$ stochastisch 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 _{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 ${\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 der Konvexität der 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.

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

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

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