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.
Seien
stochastisch unabhängige Zufallsvariablen, so dass fast sicher
gilt.
Sei ferner
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).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0058bcc2a808d7387a496c10cd73f3cac210f0c3)
Dieser Beweis folgt der Darstellung von D. Pollard, siehe auch Lutz Dümbgens Skriptum (siehe Literatur).
Betrachte zur Vereinfachung der Schreibweise die Zufallsvariablen
mit
und ferner für ein zunächst beliebiges
die auf den reellen Zahlen
monoton wachsende Abbildung
. 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].}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d3ce7fff4e4b48028203167ce1ee7d76e39a067b)
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}),}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a6781843315d12d0f754650a09681341ee6c3e37)
und mit
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)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f25053f113b2c6f25aa9b95363a6aac0e9608cfa)
für die Konstanten
und
.
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),}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9a361dfab6b44e11268f9a5b08da1cbf7ccd4876)
so kann man mittels Kurvendiskussion und Taylor-Reihenentwicklung zeigen, dass stets
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),}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ee5ec16874e54c1c79ef829298f269ef14022acb)
was bei einer Wahl von
zur zu beweisenden Behauptung führt.
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
beantwortet werden, wobei
stochastisch unabhängige und identisch verteilte Zufallsvariablen mit der Verteilung
für
sind. Dabei gilt
. Für die Berechnung der gesuchten Wahrscheinlichkeit
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
durch eine Normalverteilung mit demselben Erwartungswert und derselben Varianz approximiert. Die Verteilung der Zufallsvariablen
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]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/11fce63fb45ad9e49cb42852a7df65fec25e6153)
![{\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}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6e96e430aacb90ee65763984d68dbe0bf6506968)
- Somit ist
eine Oberschranke für die mit der Frage gesuchte Wahrscheinlichkeit, die erheblich kleiner als die angegebene Oberschranke sein kann.
- 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.