## Azuma-Hoeffding Inequality

Several posts ago, I proved Hoeffding’s inequality for independent random variables $X_{1},\cdots,X_{n}$ almost surely lying in the compact intervals $[a_{1},b_{1}],\cdots,[a_{n},b_{n}]$. Using some calculus and basic probability theory, we were able to show that

$\displaystyle\mathbb{P}\left(S_{n}-\mathbb{E}[S_{n}]\geq t\right)\leq\exp\left(-\dfrac{2t^{2}}{\sum_{j=1}^{n}(b_{j}-a_{j})^{2}}\right)$

and

$\displaystyle\mathbb{P}\left(\left|S_{n}-\mathbb{E}[S_{n}]\right|\geq t\right)\leq 2\exp\left(-\dfrac{2t^{2}}{\sum_{j=1}^{n}(b_{j}-a_{j})^{2}}\right)$

for all $t>0$. We generalize Hoeffding’s inequality to the case where $X_{1},\cdots,X_{n}$ are not necessarily independent but instead form a martingale. This result is known as the Azuma-Hoeffding inequality.

The reader of my post Hoeffding’s inequality will recall that in order to prove Hoeffding’s inequality, we needed Hoeffding’s lemma. Similarly, in order to prove the Azuma-Hoeffding inequality, we will need a generalization of Hoeffding’s lemma to conditional expectation.

Lemma 1. (Generalized Hoeffding Lemma) Let $V,Z$ be random variables such that $\mathbb{E}[V\mid Z]=0$ and $\mathbb{P}(f(Z)+a\leq V\leq f(Z)+b)=1$, for some measurable function $f:\mathbb{R}\rightarrow\mathbb{R}$ and finite constants $a,b$. Then

$\displaystyle\mathbb{E}\left[e^{\xi V}\mid Z\right]\leq e^{\frac{\xi^{2}(b-a)^{2}}{8}},\indent\forall\xi >0$

Proof. Note that the function $f(x) := e^{\xi x}$ is convex on $[a,b]$, since

$\displaystyle f'(x)=\xi e^{\xi x}\Longrightarrow \displaystyle f''(x)=\xi^{2}e^{\xi x}\geq 0, \indent \displaystyle\forall x \in \left[a,b\right]$

Since $\frac{b-x}{b-a}+\frac{x-a}{b-a}=1$, we have by convexity that

$\displaystyle e^{\xi x}=e^{\xi a\frac{b-x}{b-a}+\xi b\frac{a-x}{b-a}}\leq\dfrac{x-a}{b-a}e^{\xi b}+\dfrac{b-x}{b-a}e^{\xi a}$

Since $\mathbf{1}_{\left\{f(Z)+a\leq V\leq f(Z)+b\right\}}$ is $\sigma(Z)$-measurable, we have, almost surely, that

$\begin{array}{lcl}\displaystyle\mathbb{E}[e^{\xi V}\mid Z]&=&\displaystyle\mathbb{E}[e^{\xi V}\mid Z]\mathbf{1}_{\left\{f(Z)+a\leq V\leq f(Z)+b\right\}}\\[.7 em]&=&\displaystyle\mathbb{E}\left[e^{\xi V}\mathbf{1}_{\left\{f(Z)+a\leq V\leq f(Z)+b\right\}}\mid Z\right]\\[.7 em]&\leq&\displaystyle\mathbb{E}\left[\left(\dfrac{V-f(Z)-a}{b-a}e^{\xi(f(Z)+b)}+\dfrac{f(Z)+b-V}{b-a}e^{\xi(f(Z)+a)}\right)\mid Z\right]\\[.9 em]&=&\displaystyle\dfrac{-(f(Z)+a)}{b-a}e^{\xi(f(Z)+b)}+\dfrac{f(Z)+b}{b-a}e^{\xi(f(Z)+a)}\text{ a.s.}\end{array}$

since $\mathbb{E}[V\mid Z]=0$ a.s. Note that

$\displaystyle a\leq\mathbb{E}[V-f(Z)\mid Z]\leq\mathbb{E}[b\mid Z]=b\text{ a.s}$

so that $a \leq -\mathbb{E}[f(Z)\mid Z]\leq b$, since $\mathbb{E}[V\mid Z]=0$ a.s. Hence, $a\leq -f(Z)\leq b$, a.s. Thus, $p:= -\frac{f(Z)+a}{b-a}\in [0,1]$. With some algebraic manipulation, we can write

$\displaystyle pe^{\xi(f(Z)+b)}+(1-p)e^{\xi(f(Z)+a)}=e^{-\xi p(b-a)}\left[1-p+pe^{\xi(b-a)}\right]=e^{-p u+\log(1-p+pe^{u})},$

where $u:= \xi(b-a)$. Define a function $\phi: [0,\infty) \rightarrow \mathbb{R}$ by

$\displaystyle\phi(u):=\dfrac{u^{2}}{8}-up+\log\left(1-p+pe^{u}\right)$

Observe that $\phi(0)=0$ and

$\begin{array}{lcl}\displaystyle\phi'(u)=\dfrac{u}{4}-p+\dfrac{pe^{u}}{1-p+pe^{u}}\geq\dfrac{u}{4}-p+\dfrac{pe^{u}}{(1-p)e^{u}+pe^{u}}&=&\dfrac{u}{4}-p+\dfrac{pe^{u}}{e^{u}}\\&=&\displaystyle\dfrac{u}{4}\\&\geq&\displaystyle 0\end{array}$

so that $\phi(u)\geq 0$ for all $u\in [0,\infty)$. $\Box$

Theorem 2. Suppose $\left\{X_{n}\right\}_{n=0}^{\infty}$ is a martingale such that $\left|X_{j}-X_{j-1}\right| \leq c_{j}$, where the $c_{j}$ are positive constants.  Then for any $t > 0$ and $n\geq 1$,

$\displaystyle\mathbb{P}\left(\max_{0\leq j \leq n}\left|X_{j}\right|\geq t\right)\leq 2\exp\left(-\dfrac{t^{2}}{\sum_{j=1}^{n}c_{j}^{2}}\right)$

Proof. Observe that, for $\xi > 0$,

$\displaystyle\left\{\max_{0\leq j\leq n}\left|X_{j}\right|\geq t\right\}=\left\{\max_{0\leq j\leq n}e^{\xi X_{j}}\geq e^{\xi t}\right\}\cup\left\{\max_{0\leq j\leq n}e^{\xi X_{j}}\geq e^{-\xi t}\right\}$

Note that the functions $x \mapsto e^{x}$ and $x \mapsto e^{-x}$ are convex, so by conditional Jensen’s inequality, $e^{\xi X_{j}}, e^{-\xi X_{j}}$ are submartingales, for $\xi > 0$. By Doob’s maximality inequality, we have for all $\xi > 0$ that

$\begin{array}{lcl}\displaystyle\mathbb{P}\left(\max_{0\leq j\leq n}\left|X_{j}\right|\geq t\right)&\leq&\displaystyle\mathbb{P}\left(\max_{0\leq j\leq n}e^{\xi X_{j}}\geq e^{\xi t}\right)+\mathbb{P}\left(\max_{0\leq j\leq n}e^{-\xi X_{j}}\geq e^{\xi t}\right)\\[.7 em]&\leq&\displaystyle e^{-\xi t}\left(\mathbb{E}[e^{\xi X_{n}}]+\mathbb{E}[e^{-\xi X_{n}}]\right)\end{array}$

Set $V_{j}:=X_{j}-X_{j-1}$, so that $X_{n}=\sum_{j=1}^{n}V_{j}$. Note that $\mathbb{E}[V_{n}\mid X_{0},\cdots,X_{n}]=0$ by the martingale property of $\left\{X_{n}\right\}$. Applying the generalized Hoeffding lemma to $\mathbb{E}[e^{\xi V_{n}}\mid X_{0},\cdots,X_{n}]$, we obtain the upper bound

$\begin{array}{lcl}\displaystyle e^{-\xi t}\mathbb{E}[e^{\xi X_{n}}]=e^{-\xi t}\mathbb{E}\left[\mathbb{E}[e^{\xi\sum_{j=1}^{n}V_{j}}\mid X_{0},\cdots,X_{n}]\right]&=&\displaystyle e^{-\xi t}\mathbb{E}\left[e^{\xi\sum_{j=1}^{n-1}V_{j}}\mathbb{E}[e^{\xi V_{n}}\mid X_{0},\cdots,X_{n}]\right]\\[.9 em]&\leq&\displaystyle e^{-\xi t}\mathbb{E}\left[e^{\xi\sum_{j=1}^{n-1}V_{n}}e^{\frac{\xi^{2}(2c_{n})^{2}}{8}}\right]\\[.9 em]&=&\displaystyle e^{-\xi t}\mathbb{E}\left[e^{\xi \sum_{j=1}^{n-1}V_{n}}e^{\frac{\xi^{2}(c_{n})^{2}}{2}}\right]\end{array}$

Repeating the argument $n-1$ more times, we see that

$\displaystyle e^{-\xi t}\mathbb{E}[e^{\xi X_{n}}]\leq e^{-\xi t}e^{\xi^{2}\sum_{j=1}^{n}\frac{c_{j}^{2}}{2}}$

A completely analogous argument shows that $e^{-\xi t}\mathbb{E}[e^{-\xi X_{n}}]\leq e^{\xi^{2}\sum_{j=1}^{n}\frac{c_{j}^{2}}{2}}$, which implies that

$\displaystyle\mathbb{P}\left(\max_{0\leq j \leq n}\left|X_{j}\right| \geq t\right)\leq 2e^{-\xi t}e^{\xi^{2}\sum_{j=1}^{n}\frac{c_{j}^{2}}{2}}$

We now turn to finding the optimal choice of $\xi$ which minimizes the RHS of the inequality. Set $\alpha:=\sum_{j=1}^{n}{\frac{c_{j}^{2}}{2}}$. Then

$\displaystyle f(\xi):=\xi^{2}\alpha-\xi t=\alpha\left(\xi-\dfrac{t}{2\alpha}\right)^{2}-\dfrac{t^{2}}{4\alpha},$

which is minimal at $\xi = \frac{t}{2\alpha}$. We conclude that

$\displaystyle\mathbb{P}\left(\max_{0\leq j\leq n}\left|X_{j}\right|\geq t\right)\leq 2\exp\left(-\dfrac{t^{2}}{4\sum_{j=1}^{n}\frac{c_{j}^{2}}{2}}\right)=2\exp\left(-\dfrac{t^{2}}{2\sum_{j=1}^{n}c_{j}^{2}}\right)$

which completes the proof. $\Box$