Ungleichung von Azuma-Hoeffding

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 ${\displaystyle (X_{n},{\mathcal {F}}_{n})_{n\geq 0}}${\displaystyle (X_{n},{\mathcal {F}}_{n})_{n\geq 0}} ein Supermartingal, dessen Zuwächse ${\displaystyle X_{n}-X_{n-1}}${\displaystyle X_{n}-X_{n-1}} durch eine nichtnegative reellwertige Folge ${\displaystyle (c_{n})_{n\in \mathbb {N} }\subset [0,\infty )}${\displaystyle (c_{n})_{n\in \mathbb {N} }\subset [0,\infty )} beschränkt werden, d. h. ${\displaystyle |X_{n}-X_{n-1}|\leq c_{n}}${\displaystyle |X_{n}-X_{n-1}|\leq c_{n}} für alle ${\displaystyle n\geq 1}${\displaystyle n\geq 1} erfüllt.

Mit der Setzung ${\displaystyle d_{n}^{2}:=c_{1}^{2}+\cdots +c_{n}^{2}}${\displaystyle d_{n}^{2}:=c_{1}^{2}+\cdots +c_{n}^{2}} gilt nun, dass

(1) ${\displaystyle P(X_{n}-X_{0}\geq t)\leq \exp \left(-{\frac {t^{2}}{2d_{n}^{2}}}\right),\quad t\geq 0,n\in \mathbb {N} .}${\displaystyle P(X_{n}-X_{0}\geq t)\leq \exp \left(-{\frac {t^{2}}{2d_{n}^{2}}}\right),\quad t\geq 0,n\in \mathbb {N} .}

(2) Ist ${\displaystyle (X_{n})_{n\geq 0}}${\displaystyle (X_{n})_{n\geq 0}} ein Martingal, gilt außerdem: ${\displaystyle P(|X_{n}-X_{0}|\geq t)\leq 2\exp \left(-{\frac {t^{2}}{2d_{n}^{2}}}\right),\quad t\geq 0,n\in \mathbb {N} .}${\displaystyle P(|X_{n}-X_{0}|\geq t)\leq 2\exp \left(-{\frac {t^{2}}{2d_{n}^{2}}}\right),\quad t\geq 0,n\in \mathbb {N} .}

Bemerkung: Lässt sich ${\displaystyle X_{n}-X_{n-1}}${\displaystyle X_{n}-X_{n-1}} durch Folgen ${\displaystyle a_{n}}${\displaystyle a_{n}} und ${\displaystyle b_{n}}${\displaystyle b_{n}} beschränken, d. h. gilt ${\displaystyle a_{n}\leq X_{n}-X_{n-1}\leq b_{n}}${\displaystyle a_{n}\leq X_{n}-X_{n-1}\leq b_{n}}, kann man ${\displaystyle c_{n}=\max\{|a_{n}|,|b_{n}|\}}${\displaystyle c_{n}=\max\{|a_{n}|,|b_{n}|\}} wählen.

In der Literatur finden sich verschiedene Beweise. Der folgende Beweis folgt der Darstellung in Schilling (2018).

Da ${\displaystyle x\mapsto e^{tx}}${\displaystyle x\mapsto e^{tx}} für ${\displaystyle t\geq 0}${\displaystyle t\geq 0} und ${\displaystyle x\in \mathbb {R} }${\displaystyle x\in \mathbb {R} } konvex ist, gilt für ${\displaystyle -c\leq x\leq c}${\displaystyle -c\leq x\leq c} dass ${\displaystyle e^{tx}\leq {\frac {e^{tc}-e^{-tc}}{2c}}x+{\frac {1}{2}}(e^{tc}+e^{-tc})}${\displaystyle e^{tx}\leq {\frac {e^{tc}-e^{-tc}}{2c}}x+{\frac {1}{2}}(e^{tc}+e^{-tc})}.

Setze ${\displaystyle x=X_{n}-X_{n-1}}${\displaystyle x=X_{n}-X_{n-1}} und ${\displaystyle c=c_{n}}${\displaystyle c=c_{n}} in die Ungleichung ein und bilde den bedingten Erwartungswert bzgl. ${\displaystyle {\mathcal {F}}_{n-1}}${\displaystyle {\mathcal {F}}_{n-1}}, so folgt

${\displaystyle E(e^{t(X_{n}-X_{n-1})}|{\mathcal {F}}_{n-1})\leq \underbrace {\frac {e^{tc_{n}}-e^{-tc_{n}}}{2c_{n}}} _{\geq 0}\underbrace {E(X_{n}-X_{n-1}|{\mathcal {F}}_{n-1})} _{\leq 0}+{\frac {e^{tc_{n}}-e^{-tc_{n}}}{2}}\leq {\frac {e^{tc_{n}}-e^{-tc_{n}}}{2}}}${\displaystyle E(e^{t(X_{n}-X_{n-1})}|{\mathcal {F}}_{n-1})\leq \underbrace {\frac {e^{tc_{n}}-e^{-tc_{n}}}{2c_{n}}} _{\geq 0}\underbrace {E(X_{n}-X_{n-1}|{\mathcal {F}}_{n-1})} _{\leq 0}+{\frac {e^{tc_{n}}-e^{-tc_{n}}}{2}}\leq {\frac {e^{tc_{n}}-e^{-tc_{n}}}{2}}}.

Aus der Ungleichung ${\displaystyle (2k)!\geq 2^{k}k!}${\displaystyle (2k)!\geq 2^{k}k!} folgt ${\displaystyle {\frac {1}{2}}(e^{-y}+e^{y})=\sum \limits _{k=0}^{\infty }{\frac {y^{2k}}{(2k)!}}\leq \sum \limits _{k=0}^{\infty }{\frac {y^{2k}}{2^{k}k!}}=e^{y^{2}/2}}${\displaystyle {\frac {1}{2}}(e^{-y}+e^{y})=\sum \limits _{k=0}^{\infty }{\frac {y^{2k}}{(2k)!}}\leq \sum \limits _{k=0}^{\infty }{\frac {y^{2k}}{2^{k}k!}}=e^{y^{2}/2}} und damit ${\displaystyle E(e^{t(X_{n}-X_{n-1})}|{\mathcal {F}}_{n})\leq e^{t^{2}c_{n}^{2}/2}}${\displaystyle E(e^{t(X_{n}-X_{n-1})}|{\mathcal {F}}_{n})\leq e^{t^{2}c_{n}^{2}/2}}.

Mit der Turmeigenschaft und der Eigenschaft des „Herausziehens von Bekanntem" des bedingten Erwartungswerts erhält man:

${\displaystyle E\left(e^{t(X_{n}-X_{0})}\right)=E\left(\prod \limits _{i=1}^{n}e^{t(X_{i}-X_{i-1})}\right)=E\left(\prod \limits _{i=1}^{n-1}e^{t(X_{i}-X_{i-1})}E(e^{t(X_{n}-X_{n-1})}|{\mathcal {F}}_{n-1})\right)\leq E\left(\prod \limits _{i=1}^{n-1}e^{t(X_{i}-X_{i-1})}\right)e^{t^{2}c_{n}^{2}/2}\leq \cdots \leq e^{t^{2}d_{n}^{2}/2}}${\displaystyle E\left(e^{t(X_{n}-X_{0})}\right)=E\left(\prod \limits _{i=1}^{n}e^{t(X_{i}-X_{i-1})}\right)=E\left(\prod \limits _{i=1}^{n-1}e^{t(X_{i}-X_{i-1})}E(e^{t(X_{n}-X_{n-1})}|{\mathcal {F}}_{n-1})\right)\leq E\left(\prod \limits _{i=1}^{n-1}e^{t(X_{i}-X_{i-1})}\right)e^{t^{2}c_{n}^{2}/2}\leq \cdots \leq e^{t^{2}d_{n}^{2}/2}}.

Die Markov-Ungleichung liefert für ${\displaystyle t,\xi \geq 0}${\displaystyle t,\xi \geq 0} zuletzt: ${\displaystyle P(X_{n}-X_{0}\geq t)=P(e^{\xi (X_{n}-X_{0})}\geq e^{t\xi })\leq e^{-t\xi }E\left(e^{\xi (X_{n}-X_{0})}\right)\leq e^{-t\xi +\xi ^{2}d_{n}^{2}/2}=e^{-{\frac {1}{2}}t^{2}/d_{n}^{2}+1/2(\xi d_{n}-t/d_{n})^{2}}}${\displaystyle P(X_{n}-X_{0}\geq t)=P(e^{\xi (X_{n}-X_{0})}\geq e^{t\xi })\leq e^{-t\xi }E\left(e^{\xi (X_{n}-X_{0})}\right)\leq e^{-t\xi +\xi ^{2}d_{n}^{2}/2}=e^{-{\frac {1}{2}}t^{2}/d_{n}^{2}+1/2(\xi d_{n}-t/d_{n})^{2}}}.

Minimiert man ${\displaystyle -{\frac {1}{2}}t^{2}/d_{n}^{2}+1/2(\xi d_{n}-t/d_{n})^{2}}${\displaystyle -{\frac {1}{2}}t^{2}/d_{n}^{2}+1/2(\xi d_{n}-t/d_{n})^{2}} in ${\displaystyle \xi }${\displaystyle \xi }, nimmt die rechte Seite wegen der Monotonie bei ${\displaystyle \xi =t/d_{n}^{2}}${\displaystyle \xi =t/d_{n}^{2}} ihr Minimum an und (1) ist gezeigt.

Ist ${\displaystyle (X_{n})_{n\geq 0}}${\displaystyle (X_{n})_{n\geq 0}} ein Martingal, so ist ${\displaystyle -X_{n}}${\displaystyle -X_{n}} ein Supermartingal, d. h. es gilt ${\displaystyle P(X_{n}-X_{0}\leq -t)\leq \exp(-t^{2}/(2d_{n}^{2}))}${\displaystyle P(X_{n}-X_{0}\leq -t)\leq \exp(-t^{2}/(2d_{n}^{2}))}. 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.

1. ↑ 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 . 
2. ↑ Azuma, Kazuoki: Weighted Sums of Certain Dependent Random Variables. In: Tohoku Mathematical Journal. 1967, S. 357–367, doi:10.2748/tmj/1178243286 . 
3. ↑ Klaus Schürger: Wahrscheinlichkeitstheorie. De Gruyter, 1998, S. 428–436. 

• Stochastik
• Ungleichung (Stochastik)
• Martingale und Martingaltheorie