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
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.