Several posts ago, I proved Hoeffding’s inequality for independent random variables almost surely lying in the compact intervals . Using some calculus and basic probability theory, we were able to show that

and

for all . We generalize Hoeffding’s inequality to the case where 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 be random variables such that and , for some measurable function and finite constants . Then

*Proof. *Note that the function is convex on , since

Since , we have by convexity that

Since is -measurable, we have, almost surely, that

since a.s. Note that

so that , since a.s. Hence, , a.s. Thus, . With some algebraic manipulation, we can write

where . Define a function by

Observe that and

so that for all .

**Theorem 2. **Suppose is a martingale such that , where the are positive constants. Then for any and ,

*Proof. *Observe that, for ,

Note that the functions and are convex, so by conditional Jensen’s inequality, are submartingales, for . By Doob’s maximality inequality, we have for all that

Set , so that . Note that by the martingale property of . Applying the generalized Hoeffding lemma to , we obtain the upper bound

Repeating the argument more times, we see that

A completely analogous argument shows that , which implies that

We now turn to finding the optimal choice of which minimizes the RHS of the inequality. Set . Then

which is minimal at . We conclude that

which completes the proof.

### Like this:

Like Loading...

*Related*