Die Ungleichung von Azuma-Hoeffding ist eine Ungleichung aus der Stochastik für (Super-)martingale, deren Zuwächse beschränkt sind. Wassily Hoeffding bewies die Ungleichung 1963 für unabhängige Zufallsvariablen.[1] 1967 konnte Kazuoki Azuma das Resultat auf die Martingaltheorie erweitern.[2] Sie gehört zur Klasse der „Konzentrationsungleichungen“.
Sei
ein Supermartingal, dessen Zuwächse
durch eine nichtnegative reellwertige Folge
beschränkt werden, d. h.
für alle
erfüllt.
Mit der Setzung
gilt nun, dass
(1)
(2) Ist
ein Martingal, gilt außerdem:
Bemerkung: Lässt sich
durch Folgen
und
beschränken, d. h. gilt
, kann man
wählen.
In der Literatur finden sich verschiedene Beweise. Der folgende Beweis folgt der Darstellung in Schilling (2018).
Da
für
und
konvex ist, gilt für
dass
.
Setze
und
in die Ungleichung ein und bilde den bedingten Erwartungswert bzgl.
, so folgt
.
Aus der Ungleichung
folgt
und damit
.
Mit der Turmeigenschaft und der Eigenschaft des „Herausziehens von Bekanntem“ des bedingten Erwartungswerts erhält man:
.
Die Markov-Ungleichung liefert für
zuletzt:
.
Minimiert man
in
, nimmt die rechte Seite wegen der Monotonie bei
ihr Minimum an und (1) ist gezeigt.
Ist
ein Martingal, so ist
ein Supermartingal, d. h. es gilt
. Addiert man dies und (1), folgt auch die Behauptung in (2).
Die Azuma-Hoeffding-Ungleichung lässt sich auf stochastische Varianten kombinatorischer Optimierungsprobleme, u. a. das Problem des Handlungsreisenden oder Matching-Probleme, anwenden.[3]
- René L. Schilling: Martingale und Prozesse, De Gruyter, 2018, S. 91–92.
- Ludger Rüschendorf: Wahrscheinlichkeitstheorie, Springer Berlin/Heidelberg, 2016, S. 360–361.
- Klaus Schürger: Wahrscheinlichkeitstheorie, De Gruyter, 1998, S. 382–385.
- ↑ Hoeffding, Wassily: Probability inequalities for sums of bounded random variables. In: Journal of the American Statistical Association. 1963, S. 13–30, doi:10.2307/2282952.
- ↑ Azuma, Kazuoki: Weighted Sums of Certain Dependent Random Variables. In: Tohoku Mathematical Journal. 1967, S. 357–367, doi:10.2748/tmj/1178243286.
- ↑ Klaus Schürger: Wahrscheinlichkeitstheorie. De Gruyter, 1998, S. 428–436.