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 Zufallsvariablen, so dass stets gilt. Sei ferner eine positive, reellwertige Konstante. Dann gilt:
![{\displaystyle a_{i}\leq X_{i}-{\textrm {E}}[X_{i}]\leq b_{i}}](/media/api/rest_v1/media/math/render/svg/49bb707b77508669b14bffe4a98a932ba95828ac)
![{\displaystyle {\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).}](/media/api/rest_v1/media/math/render/svg/4446e9f4aa9c397b4320e7cf68da871d5656c205)
Beispiele
- Betrachte die folgende Frage: Wie wahrscheinlich ist es, bei hundertmaligem Würfeln wenigstens eine Augensumme von 500 zu erreichen? Beschreibt den Würfelwurf mit so folgt mit der Hoeffding-Ungleichung:
![{\displaystyle E[X]=3,5}](/media/api/rest_v1/media/math/render/svg/761288bfe0067b3fa6be25c0e1e37c383aa535e3)
![{\displaystyle {\textrm {prob}}\left[\sum X\geq 500\right]}](/media/api/rest_v1/media/math/render/svg/6cda4a2ace26f41ed94af1cda93ebfdb88f08a8b)
![{\displaystyle ={\textrm {prob}}\left[\sum X-E[X]\geq 150\right]}](/media/api/rest_v1/media/math/render/svg/e077760c81340059447f7d038b010cbef633ed92)
