Hoeffding-Ungleichung

In der Wahrscheinlichkeitstheorie beschreibt die Hoeffding-Ungleichung (nach Hoeffding) die maximale Wahrscheinlichkeit, dass eine Summe von unabhängigen, zentrierten und beschränkten Zufallsvariablen stärker als eine Konstante von ihrem Erwartungswert abweicht.

Definition

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

${\textrm {prob}}\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).$

Beispiele

• Betrachte die folgende Frage: Wie wahrscheinlich ist es, bei hundertmaligem Würfeln wenigstens eine Augensumme von 500 zu erreichen? Beschreibt $X$ den Würfelwurf mit $E[X]=3,5$ so folgt mit der Hoeffding-Ungleichung:

${\textrm {prob}}\left[\sum X\geq 500\right]$ $={\textrm {prob}}\left[\sum X-E[X]\geq 150\right]$

$\leq {\textrm {exp}}\left({\frac {-2\cdot 150^{2}}{\sum (6-1)^{2}}}\right)$ $={\textrm {exp}}\left({\frac {-45000}{100\cdot 25}}\right)$ $={\textrm {exp}}\left(-18\right)\approx 1,52\ldots \cdot 10^{-8}$