Azuma-Hoeffding Bounds for Martingales

Why Bounded Martingale Increments Matter

For independent bounded variables, concentration can be derived by controlling the exponential moments of their sum. Martingales allow dependence: each new increment may depend on the entire past, but its conditional mean, given that past, is zero. If every increment is also bounded, the same exponential-moment strategy yields a useful tail bound. This is the Azuma-Hoeffding inequality.

The bound is useful when a statistic can be revealed in stages and its successive conditional-expectation changes are controlled. Independence is not required. What matters is the martingale property and an almost-sure bound on each increment.

Martingales and Bounded Increments

Definition: Let $(\mathcal{F}_i)_{i=0}^n$ be a filtration, meaning an increasing sequence of sigma-fields. An integrable sequence $(M_i)_{i=0}^n$ is a martingale with respect to this filtration if $M_i$ is $\mathcal{F}_i$-measurable and $E[M_i\mid\mathcal{F}_{i-1}]=M_{i-1}$ almost surely for every $i=1,\ldots,n$. Its increments are $D_i=M_i-M_{i-1}$; they satisfy $E[D_i\mid\mathcal{F}_{i-1}]=0$ almost surely.

A deterministic sequence $c_1,\ldots,c_n$ bounds the increments if each $c_i\geq 0$ and $P(|D_i|\leq c_i)=1$. Define $V=\sum_{i=1}^n c_i^2$. The constants can vary from step to step, which is important when some changes are more tightly controlled than others.

Theorem (Azuma-Hoeffding inequality): Suppose $(M_i)_{i=0}^n$ is an integrable martingale with respect to $(\mathcal{F}_i)_{i=0}^n$, and $|M_i-M_{i-1}|\leq c_i$ almost surely for deterministic $c_i\geq 0$. If $V=\sum_{i=1}^n c_i^2>0$, then for every $t\geq 0$, $$ P(M_n-M_0\geq t)\leq \exp\left(-\frac{t^2}{2V}\right), \qquad P(M_n-M_0\leq -t)\leq \exp\left(-\frac{t^2}{2V}\right). $$ Consequently, $$ P(|M_n-M_0|\geq t)\leq 2\exp\left(-\frac{t^2}{2V}\right). $$ If $V=0$, all increments are zero almost surely, so $M_n=M_0$ almost surely.

The Exponential-Moment Bound Behind the Inequality

The key step is a conditional version of Hoeffding’s lemma. A centered random variable confined to a short interval cannot have an arbitrarily large exponential moment. The conditional form is what allows the argument to accommodate dependence on the past.

Lemma (conditional Hoeffding bound): If $Y$ is measurable and integrable, $E[Y\mid\mathcal{G}]=0$ almost surely, and $|Y|\leq c$ almost surely for a deterministic $c\geq 0$, then for every real $\lambda$, $$ E[e^{\lambda Y}\mid\mathcal{G}] \leq \exp\left(\frac{\lambda^2c^2}{2}\right) \quad\text{almost surely}. $$

Proof. When $c=0$, $Y=0$ almost surely and the result holds with equality. Suppose $c>0$. For every $y\in[-c,c]$, convexity of the exponential function bounds its value by the chord joining its values at $-c$ and $c$: $$ e^{\lambda y} \leq \frac{c+y}{2c}e^{\lambda c} +\frac{c-y}{2c}e^{-\lambda c}. $$ Take conditional expectations given $\mathcal{G}$. Since $E[Y\mid\mathcal{G}]=0$, the coefficients on the right each have conditional expectation $1/2$. Thus $$ E[e^{\lambda Y}\mid\mathcal{G}] \leq \frac{e^{\lambda c}+e^{-\lambda c}}{2} =\cosh(\lambda c). $$ For every real $x$, $\log\cosh(x)\leq x^2/2$. To see this for $x\geq 0$, the derivative of $\log\cosh(x)$ is $\tanh(x)$, and $\tanh(x)\leq x$: the difference $x-\tanh(x)$ is zero at zero and has derivative $1-\operatorname{sech}^2(x)\geq 0$. Integrating from zero to $x$ gives the inequality. Both sides are even functions, so it holds for negative $x$ as well. Therefore $\cosh(\lambda c)\leq\exp(\lambda^2c^2/2)$, proving the lemma. $\square$

Proof of the Azuma-Hoeffding Inequality

Apply the lemma to each martingale difference $D_i$, conditional on $\mathcal{F}_{i-1}$. The martingale property gives the required conditional mean zero, and the increment assumption supplies the bound $c_i$. Iterating these conditional bounds controls the exponential moment of the full sum.

Proof. Write $S=M_n-M_0=\sum_{i=1}^n D_i$. For $\lambda>0$, the conditional Hoeffding bound gives $$ E[e^{\lambda D_i}\mid\mathcal{F}_{i-1}] \leq \exp\left(\frac{\lambda^2c_i^2}{2}\right). $$ Since $\sum_{j=1}^{i-1}D_j$ is $\mathcal{F}_{i-1}$-measurable, conditioning successively yields $$ E\left[\exp\left(\lambda\sum_{j=1}^iD_j\right)\right] \leq \exp\left(\frac{\lambda^2c_i^2}{2}\right) E\left[\exp\left(\lambda\sum_{j=1}^{i-1}D_j\right)\right]. $$ Starting at $i=1$ and iterating through $n$ gives $$ E[e^{\lambda S}]\leq \exp\left(\frac{\lambda^2V}{2}\right). $$ Markov’s inequality now implies $$ P(S\geq t) =P(e^{\lambda S}\geq e^{\lambda t}) \leq \exp\left(-\lambda t+\frac{\lambda^2V}{2}\right). $$ For $t>0$, choose $\lambda=t/V$, which minimizes the exponent over $\lambda>0$. Substitution gives $P(S\geq t)\leq\exp(-t^2/(2V))$. The inequality for $t=0$ follows from $P(S\geq 0)\leq 1$. Apply the same argument to the martingale $(-M_i)_{i=0}^n$ to obtain the lower-tail bound. Finally, the event $\{|S|\geq t\}$ is contained in the union of $\{S\geq t\}$ and $\{S\leq -t\}$; adding the two one-sided bounds proves the two-sided inequality. If $V=0$, every $c_i=0$, so every $D_i=0$ almost surely. $\square$

Worked Deviation Calculations

Worked Example: A Symmetric Random Walk

Let $X_1,\ldots,X_{12}$ be independent variables, each equal to $1$ or $-1$ with probability $1/2$. Set $M_0=0$ and $M_k=\sum_{i=1}^kX_i$. With the filtration generated by the first $k$ variables, this is a martingale: each next increment has conditional mean zero. Also $|X_i|=1$, so $c_i=1$ and $V=12$.

For $t=4$, the one-sided bound is $$ P(M_{12}\geq 4)\leq \exp\left(-\frac{4^2}{2(12)}\right) =e^{-2/3}\approx 0.5134. $$ The two-sided bound is $P(|M_{12}|\geq 4)\leq 2e^{-2/3}\approx 1.0268$. Since a probability cannot exceed one, this two-sided result gives no useful numerical restriction at this threshold.

For a more stringent one-sided target of $0.025$, solve $\exp(-t^2/24)=0.025=1/40$. Taking logarithms gives $t^2=24\log(40)$, hence $$ t=\sqrt{24\log(40)}\approx 9.41 \quad\text{(more precisely, approximately }9.4092\text{)}. $$ Thus $P(M_{12}\geq 9.4092)\leq 0.025$. For a two-sided target of $0.05$, the same threshold makes each one-sided bound $0.025$, so $P(|M_{12}|\geq 9.4092)\leq 0.05$.

Worked Example: A Martingale With Different Increment Bounds

Suppose $D_1,D_2,D_3$ are conditionally symmetric increments: given the past, each $D_i$ is equally likely to be $c_i$ or $-c_i$, where $(c_1,c_2,c_3)=(1,2,1)$. Let $M_0=0$ and $M_k=\sum_{i=1}^kD_i$. Conditional symmetry makes each increment’s conditional mean zero, so $(M_k)$ is a martingale. The sum of squared bounds is $$ V=1^2+2^2+1^2=6. $$ For a deviation of at least $3$, Azuma-Hoeffding gives $$ P(M_3\geq 3)\leq e^{-9/(2\cdot 6)} =e^{-3/4}\approx 0.4724. $$ The two-sided bound is $P(|M_3|\geq 3)\leq 2e^{-3/4}\approx 0.9447$. The different increment sizes enter through their squares; replacing them by a common bound of $2$ would instead give $V=12$ and a weaker result.

Worked Example: Bounded Increments That Depend on the Past

Let $M_0=0$, and let $D_1$ equal $1$ or $-1$, each with probability $1/2$. Given $D_1=1$, let $D_2=1$ with probability $1/4$ and $D_2=-1/3$ with probability $3/4$. Given $D_1=-1$, let $D_2=1/3$ with probability $3/4$ and $D_2=-1$ with probability $1/4$. Set $M_1=D_1$, $M_2=D_1+D_2$, and use the filtration generated by $D_1$ and then by $(D_1,D_2)$.

The conditional means are zero: $$ E[D_2\mid D_1=1]=\frac14-\frac34\cdot\frac13=0, \qquad E[D_2\mid D_1=-1]=\frac34\cdot\frac13-\frac14=0. $$ Both increments have absolute value at most $1$, so $V=1^2+1^2=2$. The possible values of $M_2$ are $2$ with probability $1/8$, $2/3$ with probability $3/8$, $-2/3$ with probability $3/8$, and $-2$ with probability $1/8$. Therefore $P(M_2\geq 1)=1/8=0.125$, while the bound at $t=1$ is $$ P(M_2\geq 1)\leq \exp\left(-\frac{1}{2\cdot2}\right) =e^{-1/4}\approx 0.7788. $$ The bound is valid but conservative. The example shows that dependence of the next increment on the past is allowed, provided its conditional mean is zero and its absolute value is bounded.

Common Mistakes and Practical Interpretation

Azuma-Hoeffding turns bounds on individual changes into a tail bound on their sum. The dependence structure may be complex, but the proof uses only conditional centering and bounded increments. In applications, the difficult work is often establishing valid $c_i$'s; they must hold almost surely, not merely with high probability.

Confusing boundedness with conditional centering. Bounded increments alone do not make a process a martingale. One must also check $E[D_i\mid\mathcal{F}_{i-1}]=0$ almost surely.
Using the wrong constant. With $|D_i|\leq c_i$, the exponent is $-t^2/(2\sum_i c_i^2)$. A bound on the interval width is a different way of specifying the assumption and changes how the constant is written.
Forgetting the tail direction. The one-sided upper-tail bound has no factor of $2$. The factor appears when combining upper and lower tails for $|M_n-M_0|$.
Assuming a useful numerical bound is guaranteed. A valid upper bound can exceed one, as in the first example’s two-sided calculation. In that case it remains correct but does not improve on the basic probability bound.

Key takeaway: If a martingale has increments bounded in absolute value by $c_i$, then its deviation after $n$ steps has one-sided tail at most $\exp(-t^2/(2\sum_i c_i^2))$. Independence is unnecessary, but conditional mean zero is essential.

Check Your Understanding

Use the martingale condition and the increment bounds explicitly in each answer.

If $n=8$ and every increment satisfies $|D_i|\leq 2$, what value of $V$ enters the Azuma-Hoeffding bound?
State the one-sided upper-tail bound when the increment limits are $c_1,\ldots,c_n$.
Why does boundedness of each increment, by itself, not establish that a sequence is a martingale?
For $V=5$ and $t=2$, calculate the Azuma-Hoeffding upper bound for $P(M_n-M_0\geq 2)$.
When is the factor of $2$ included in the Azuma-Hoeffding probability bound?