Azuma-Hoeffding Inequality from Conditional Moment Bounds

From Bounded Increments to Tail Bounds

A martingale has no predictable drift: conditional on the information available at time $n-1$, its next increment has mean zero. This does not prevent a large accumulated deviation, but it lets us control the exponential moment of that deviation one step at a time. If each increment lies in a known interval, the resulting bound quantifies how unlikely a large upward or downward fluctuation is.

Work on a probability space $(\Omega,\mathcal{F},\mathbb{P})$ with a filtration $(\mathcal{F}_n)_{0\le n\le N}$, an increasing sequence of sigma-fields representing information through time $n$. A finite-horizon process $(M_n)_{0\le n\le N}$ is a martingale with respect to this filtration if each $M_n$ is integrable, $M_n$ is $\mathcal{F}_n$-measurable, and $\mathbb{E}[M_n\mid\mathcal{F}_{n-1}]=M_{n-1}$ almost surely for $1\le n\le N$. Write $D_n=M_n-M_{n-1}$ for its increments. Thus $\mathbb{E}[D_n\mid\mathcal{F}_{n-1}]=0$ almost surely.

Theorem (Azuma-Hoeffding inequality): Suppose $(M_n)_{0\le n\le N}$ is a martingale and, for each $n$, there are deterministic finite numbers $a_n\le b_n$ such that $a_n\le D_n\le b_n$ almost surely. Put $V=\sum_{n=1}^N(b_n-a_n)^2$. If $V>0$, then for every $t>0$, $$ \mathbb{P}(M_N-M_0\ge t)\le \exp\!\left(-\frac{2t^2}{V}\right),\qquad \mathbb{P}(|M_N-M_0|\ge t)\le 2\exp\!\left(-\frac{2t^2}{V}\right). $$ If $V=0$, then $M_N-M_0=0$ almost surely, so both probabilities are zero for $t>0$.

The constant depends on the interval width $b_n-a_n$, not simply on an endpoint or on a vaguely specified “bound on the increment.” The proof has two parts: first control one increment’s conditional exponential moment, then combine these bounds and optimize an exponential Markov inequality.

The Conditional Exponential-Moment Bound

Lemma (Hoeffding’s conditional bound): If $D$ is integrable, $\mathcal{G}$-measurable conditional expectations are defined, $a\le D\le b$ almost surely for deterministic finite $a\le b$, and $\mathbb{E}[D\mid\mathcal{G}]=0$ almost surely, then for every real $\theta$, $$ \mathbb{E}[e^{\theta D}\mid\mathcal{G}] \le \exp\!\left(\frac{\theta^2(b-a)^2}{8}\right) \quad\text{almost surely}. $$

Proof. If $a=b$, the assumptions force $D=0$ almost surely, and both sides equal $1$. Otherwise, the conditional mean-zero assumption and the bounds imply $a\le0\le b$. By convexity, for every $x\in[a,b]$, $$ e^{\theta x}\le \frac{b-x}{b-a}e^{\theta a}+\frac{x-a}{b-a}e^{\theta b}. $$ Take conditional expectations and use $\mathbb{E}[D\mid\mathcal{G}]=0$. The result is $$ \mathbb{E}[e^{\theta D}\mid\mathcal{G}] \le \frac{b}{b-a}e^{\theta a}+\frac{-a}{b-a}e^{\theta b}. $$ The coefficients are nonnegative and sum to $1$. The expression on the right is the moment generating function of a two-point random variable $Z$ that takes values $a,b$ with probabilities $b/(b-a),-a/(b-a)$; these probabilities give $\mathbb{E}Z=0$.

To bound that expression, define $g(\theta)=\log\mathbb{E}e^{\theta Z}$. Differentiating the finite two-term sum shows that $g''(\theta)$ is the variance of $Z$ under the probabilities reweighted proportionally to $e^{\theta Z}$. Under any probabilities on $[a,b]$, the variance is at most $(b-a)^2/4$: with $c=(a+b)/2$, $\operatorname{Var}(Z)\le\mathbb{E}[(Z-c)^2]\le(b-a)^2/4$. Also $g(0)=0$ and $g'(0)=\mathbb{E}Z=0$. Taylor’s formula with integral remainder gives $$ g(\theta)=\theta^2\int_0^1(1-u)g''(u\theta)\,du \le \frac{\theta^2(b-a)^2}{4}\int_0^1(1-u)\,du =\frac{\theta^2(b-a)^2}{8}. $$ Exponentiating this inequality bounds the two-point moment generating function and proves the claim. $\square$

Proof of the Tail Inequality

Proof. If $V=0$, every interval has width zero, so each $D_n$ equals its interval endpoint almost surely. Its conditional mean is zero, so that endpoint must be zero. Hence every increment is zero almost surely. Now suppose $V>0$. Applying the lemma with $\mathcal{G}=\mathcal{F}_{n-1}$ gives $$ \mathbb{E}[e^{\theta D_n}\mid\mathcal{F}_{n-1}] \le \exp\!\left(\frac{\theta^2(b_n-a_n)^2}{8}\right) $$ for every real $\theta$. Since $M_N-M_0=\sum_{n=1}^N D_n$, successive conditioning yields $$ \mathbb{E}\exp\!\left(\theta\sum_{n=1}^N D_n\right) \le \exp\!\left(\frac{\theta^2V}{8}\right). $$ Indeed, at each step, the earlier increments are $\mathcal{F}_{n-1}$-measurable, so their exponential factor can be taken outside the conditional expectation; iterating removes one increment at a time.

For $\theta>0$, on the event $\sum_nD_n\ge t$, the exponential is at least $e^{\theta t}$. Markov’s inequality therefore gives $$ \mathbb{P}\!\left(\sum_{n=1}^ND_n\ge t\right) \le \exp\!\left(-\theta t+\frac{\theta^2V}{8}\right). $$ The exponent is minimized over $\theta>0$ at $\theta=4t/V$, which gives the one-sided bound $\exp(-2t^2/V)$. Apply that same bound to the martingale $(-M_n)$, whose increments lie in $[-b_n,-a_n]$ and have the same widths, to bound $\mathbb{P}(M_N-M_0\le-t)$. The two events $\{M_N-M_0\ge t\}$ and $\{M_N-M_0\le-t\}$ have union $\{|M_N-M_0|\ge t\}$; adding their probability bounds proves the two-sided inequality. $\square$

Applying the Bound and Tracking the Widths

Worked Example: Four Symmetric Increments

Let $D_1,\ldots,D_4$ be independent, with each increment equal to $\tfrac12$ or $-\tfrac12$, each with probability $\tfrac12$. Set $M_0=0$ and $M_n=\sum_{k=1}^nD_k$, with $\mathcal{F}_n$ the information from the first $n$ increments. Independence and the zero mean of each increment give $\mathbb{E}[D_n\mid\mathcal{F}_{n-1}]=0$, so this is a martingale. Each increment lies in $[-\tfrac12,\tfrac12]$, an interval of width $1$. Thus $V=4\cdot1^2=4$.

For $t=1$, the theorem gives $$ \mathbb{P}(M_4\ge1)\le e^{-2/4}=e^{-1/2}, \qquad \mathbb{P}(|M_4|\ge1)\le2e^{-1/2}. $$ For a direct moment check, one increment has moment generating function $\tfrac12e^{\theta/2}+\tfrac12e^{-\theta/2}$. The lemma bounds this by $e^{\theta^2/8}$; multiplying the four independent moment generating functions gives $e^{\theta^2/2}=e^{\theta^2V/8}$, as in the proof. The bound is an upper bound, not a claim that the tail probability equals either expression.

Worked Example: Asymmetric Increment Ranges

Let $D_1,D_2$ be independent, each equal to $-2$ with probability $\tfrac13$ and $1$ with probability $\tfrac23$. Set $M_0=0$, $M_n=\sum_{k=1}^nD_k$, and use the filtration generated by the increments through time $n$. The mean of either increment is $(-2)(\tfrac13)+(1)(\tfrac23)=0$, so the sums form a martingale. The exact range is $[-2,1]$, of width $3$, and $V=2\cdot3^2=18$.

At threshold $t=2$, the upper-tail bound is $$ \mathbb{P}(M_2\ge2)\le \exp\!\left(-\frac{2\cdot2^2}{18}\right)=e^{-4/9}. $$ The event occurs only when both increments equal $1$, so its probability is $(\tfrac23)^2=\tfrac49$. Thus the computed bound is $\tfrac49\le e^{-4/9}$, consistent with the theorem. In this case $M_2\ge2$ requires $M_2=2$, since the largest possible sum is $1+1=2$.

If one instead uses the enclosing interval $[-2,2]$, its width is $4$, so the same theorem gives $V=2\cdot4^2=32$ and the valid, looser bound $e^{-1/4}$. The actual interval is asymmetric, but the theorem requires only an interval containing the increments; using a wider one remains valid.

Worked Example: Different Widths at Different Times

Let $D_1$ and $D_2$ be independent, with $D_1$ equal to $-\tfrac12$ or $\tfrac12$ with equal probabilities, and $D_2$ equal to $-1$ or $1$ with equal probabilities. With $M_0=0$, $M_n=D_1+\cdots+D_n$, and the filtration generated by the increments, conditional means are zero. The respective interval widths are $1$ and $2$, so $V=1^2+2^2=5$, not $2$ times either width squared.

For $t=1$, Azuma-Hoeffding gives $$ \mathbb{P}(M_2\ge1)\le \exp\!\left(-\frac{2\cdot1^2}{5}\right)=e^{-2/5}. $$ To check the event directly, the four equally likely pairs of increments give sums $-\tfrac32,-\tfrac12,\tfrac12,\tfrac32$. Exactly one sum is at least $1$, so the probability is $\tfrac14$, which is bounded by $e^{-2/5}$. This calculation also confirms the strictness at the threshold: the value $\tfrac12$ is not counted in $\{M_2\ge1\}$.

Why the Range Constant Matters

For the common assumption $|D_n|\le c_n$, use the containing interval $[-c_n,c_n]$. Its width is $2c_n$, so the exponent in the one-sided inequality becomes $-t^2/(2\sum_n c_n^2)$. When narrower intervals are known, their actual widths can improve the bound. The martingale condition is equally important: the proof uses the zero conditional mean at each step, not merely a zero unconditional mean for the final sum.

Common mistake: confusing a maximum absolute value with an interval width. In the asymmetric example, $|D_n|\le2$ is true, but $2$ is not the width of the actual interval $[-2,1]$; that width is $3$. Incorrectly substituting $2$ as the width for both increments would give, at $t=2$, the purported bound $\exp(-2\cdot2^2/(2\cdot2^2))=e^{-1}$. Yet the probability of $M_2\ge2$ is $\tfrac49$, and $\tfrac49>e^{-1}$ (because $e>1+1+\tfrac12=\tfrac52$, so $e^{-1}<\tfrac25<\tfrac49$). That claimed bound is false. The correction is to use width $3$, giving $e^{-4/9}$, or to use the valid but wider containing interval $[-2,2]$, giving $e^{-1/4}$.

Check Your Understanding

For each question, identify the interval widths before applying the inequality.

If $D_n\in[-c_n,c_n]$ almost surely and the increments have conditional mean zero, what is the one-sided Azuma-Hoeffding bound for $M_N-M_0\ge t$?
Why does the conditional exponential-moment step require $\mathbb{E}[D_n\mid\mathcal{F}_{n-1}]=0$, rather than only $\mathbb{E}D_n=0$?
Two increments lie in $[-1,2]$ and $[-\tfrac12,\tfrac12]$, respectively. Compute $V$ and write the bound for the event that their sum is at least $t>0$.
In the asymmetric example, compute the probability of $M_2\ge1$, and compare it with the stated upper bound at $t=1$.
What does the theorem imply when every increment lies in an interval of width zero and has conditional mean zero?