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

Advertisements
This entry was posted in math.PR and tagged , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s