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“.

Aussage

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

Mit der Setzung ${\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} .}$

(2) Ist ${\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} .}$

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

Beweis

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

Da ${\displaystyle x\mapsto e^{tx}}$ für ${\displaystyle t\geq 0}$ und ${\displaystyle x\in \mathbb {R} }$ konvex ist, gilt für ${\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})}$.

Setze ${\displaystyle x=X_{n}-X_{n-1}}$ und ${\displaystyle c=c_{n}}$ in die Ungleichung ein und bilde den bedingten Erwartungswert bzgl. ${\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}}}$.

Aus der Ungleichung ${\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}}$ und damit ${\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}}$.

Die Markov-Ungleichung liefert für ${\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}}}$.

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

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

Anwendungen

Die Azuma-Hoeffding-Ungleichung lässt sich auf stochastische Varianten kombinatorischer Optimierungsprobleme, u. a. das Problem des Handlungsreisenden oder Matching-Probleme, anwenden.^[3]

Literatur

• 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.

Einzelnachweise

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.