# 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. 1967 konnte Kazuoki Azuma das Resultat auf die Martingaltheorie erweitern. Sie gehört zur Klasse der „Konzentrationsungleichungen“.

## Aussage

Sei $(X_{n},{\mathcal {F}}_{n})_{n\geq 0}$ ein Supermartingal, dessen Zuwächse $X_{n}-X_{n-1}$ durch eine nichtnegative reellwertige Folge $(c_{n})_{n\in \mathbb {N} }\subset [0,\infty )$ beschränkt werden, d. h. $|X_{n}-X_{n-1}|\leq c_{n}$ für alle $n\geq 1$ erfüllt.
Mit der Setzung $d_{n}^{2}:=c_{1}^{2}+\cdots +c_{n}^{2}$ gilt nun, dass
(1) $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 $(X_{n})_{n\geq 0}$ ein Martingal, gilt außerdem: $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 $X_{n}-X_{n-1}$ durch Folgen $a_{n}$ und $b_{n}$ beschränken, d. h. gilt $a_{n}\leq X_{n}-X_{n-1}\leq b_{n}$, kann man $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 $x\mapsto e^{tx}$ für $t\geq 0$ und $x\in \mathbb {R}$ konvex ist, gilt für $-c\leq x\leq c$ dass $e^{tx}\leq {\frac {e^{tc}-e^{-tc}}{2c}}x+{\frac {1}{2}}(e^{tc}+e^{-tc})$.
Setze $x=X_{n}-X_{n-1}$ und $c=c_{n}$ in die Ungleichung ein und bilde den bedingten Erwartungswert bzgl. ${\mathcal {F}}_{n-1}$, so folgt
$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 $(2k)!\geq 2^{k}k!$ folgt ${\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 $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:
$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 $t,\xi \geq 0$ zuletzt: $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 $-{\frac {1}{2}}t^{2}/d_{n}^{2}+1/2(\xi d_{n}-t/d_{n})^{2}$ in $\xi$, nimmt die rechte Seite wegen der Monotonie bei $\xi =t/d_{n}^{2}$ ihr Minimum an und (1) ist gezeigt.
Ist $(X_{n})_{n\geq 0}$ ein Martingal, so ist $-X_{n}$ ein Supermartingal, d. h. es gilt $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.