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,{ℱ}_n{)}_{n\ge 0}$ ein Supermartingal, dessen Zuwächse $X_n-X_{n-1}$ durch eine nichtnegative reellwertige Folge $(c_n{)}_{n\in \mathbb{N}}\subset [0,\mathrm{\infty })$ beschränkt werden, d. h. $|X_n-X_{n-1}|\le c_n$ für alle $n\ge 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\ge t)\le \exp (-\frac{t^2}{2d_n^2}),t\ge 0,n\in \mathbb{N}.$

(2) Ist $(X_n{)}_{n\ge 0}$ ein Martingal, gilt außerdem: $P(|X_n-X_0|\ge t)\le 2\exp (-\frac{t^2}{2d_n^2}),t\ge 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\le X_n-X_{n-1}\le 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\ge 0$ und $x\in ℝ$ konvex ist, gilt für $-c\le x\le c$ dass $e^{tx}\le \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. ${ℱ}_{n-1}$, so folgt

$E(e^{t(X_n-X_{n-1})}|{ℱ}_{n-1})\le \underset{\ge 0}{\underbrace{\frac{e^{t{c}_n}-e^{-t{c}_n}}{2c_n}}}\underset{\le 0}{\underbrace{E(X_n-X_{n-1}|{ℱ}_{n-1})}}+\frac{e^{t{c}_n}-e^{-t{c}_n}}{2}\le \frac{e^{t{c}_n}-e^{-t{c}_n}}{2}$.

Aus der Ungleichung $(2k)!\ge 2^{k}k!$ folgt $\frac{1}{2}(e^{-y}+e^y)=\sum _{k=0}^{\mathrm{\infty }}\frac{y^{2k}}{(2k)!}\le \sum _{k=0}^{\mathrm{\infty }}\frac{y^{2k}}{2^{k}k!}=e^{y^2/2}$ und damit $E(e^{t(X_n-X_{n-1})}|{ℱ}_n)\le 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 _{i=1}^n{e}^{t(X_i-X_{i-1})}\right)=E(\prod _{i=1}^{n-1}{e}^{t(X_i-X_{i-1})}E(e^{t(X_n-X_{n-1})}|{ℱ}_{n-1}))\le E\left(\prod _{i=1}^{n-1}{e}^{t(X_i-X_{i-1})}\right)e^{t^2{c}_n^2/2}\le \cdots \le e^{t^2{d}_n^2/2}$.

Die Markov-Ungleichung liefert für $t,\xi \ge 0$ zuletzt: $P(X_n-X_0\ge t)=P(e^{\xi (X_n-X_0)}\ge e^{t\xi })\le e^{-t\xi }E\left(e^{\xi (X_n-X_0)}\right)\le 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\ge 0}$ ein Martingal, so ist $-X_n$ ein Supermartingal, d. h. es gilt $P(X_n-X_0\le -t)\le \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.

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.