Azuma-Hoeffding vs. Freedman Inequality. Martingale Concentration Bounds

What Each Bounds

Both Azuma-Hoeffding and Freedman bound the tail probability of a martingale. Let $M_0, M_1, \ldots, M_n$ be a martingale with differences $d_i = M_i - M_{i-1}$ .

Azuma-Hoeffding uses only the bounded range of each increment.

Freedman uses both the bounded range and the cumulative conditional variance (the predictable quadratic variation).

Side-by-Side Statement

Definition

Azuma-Hoeffding Inequality

If $|d_i| \leq c_i$ almost surely for each $i$ , then:

$\Pr[|M_n - M_0| \geq t] \leq 2\exp\!\left(-\frac{t^2}{2\sum_{i=1}^n c_i^2}\right)$

For identically bounded increments $|d_i| \leq c$ :

$\Pr[|M_n - M_0| \geq t] \leq 2\exp\!\left(-\frac{t^2}{2nc^2}\right)$

Definition

Freedman's Inequality

If $|d_i| \leq R$ almost surely and $W_n = \sum_{i=1}^n \mathbb{E}[d_i^2 \mid \mathcal{F}_{i-1}]$ is the predictable quadratic variation, then for any $t, \sigma^2 > 0$ :

$\Pr[M_n - M_0 \geq t \text{ and } W_n \leq \sigma^2] \leq \exp\!\left(-\frac{t^2/2}{\sigma^2 + Rt/3}\right)$

Where Each Is Stronger

Azuma-Hoeffding wins on simplicity

Azuma-Hoeffding requires one piece of information per increment: the bound $c_i$ . There is no conditional variance to track or bound. The statement is clean and the proof is a direct application of Hoeffding's lemma to martingale differences. When you have bounded increments and no variance information, Azuma-Hoeffding is the right choice.

Freedman wins when variance is small

Consider a martingale where each increment $d_i$ is bounded by $c$ but has conditional variance $\sigma_i^2 \ll c^2$ . Azuma-Hoeffding treats the increment as if it could take any value in $[-c, c]$ with equal ease. Freedman knows the increment is usually small.

For concreteness, suppose $|d_i| \leq 1$ but $\mathbb{E}[d_i^2 \mid \mathcal{F}_{i-1}] \leq v$ for some $v \ll 1$ . After $n$ steps:

	Azuma exponent	Freedman exponent
Deviation $t$	$-t^2/(2n)$	$-t^2/(2nv + 2t/3)$

When $v \ll 1$ and $t$ is moderate, Freedman is tighter by a factor of roughly $1/v$ .

The Two Regimes of Freedman

Theorem

Freedman's Two Regimes

Statement

Freedman's bound $\exp(-t^2/(2\sigma^2 + 2Rt/3))$ interpolates between two behaviors:

Small deviations ( $t \ll 3\sigma^2/R$ ): The denominator $\sigma^2 + Rt/3 \approx \sigma^2$ , giving:

$\Pr[\ldots] \lesssim \exp\!\left(-\frac{t^2}{2\sigma^2}\right)$

This is a sub-Gaussian tail with the actual variance, not the worst-case variance from the bounded range.

Large deviations ( $t \gg 3\sigma^2/R$ ): The denominator $\sigma^2 + Rt/3 \approx Rt/3$ , giving:

$\Pr[\ldots] \lesssim \exp\!\left(-\frac{3t}{2R}\right)$

This is a sub-exponential (Poisson-like) tail, linear in $t$ .

Intuition

Near the mean, the martingale behaves like a Gaussian with its true variance. Far from the mean, the bounded increments cause the tail to transition from Gaussian ( $e^{-t^2}$ ) to exponential ( $e^{-t}$ ). Azuma-Hoeffding gives a single Gaussian-like bound everywhere, but with the worst-case variance $c^2$ instead of the true conditional variance. Freedman captures the correct behavior in both regimes.

Failure Mode

Freedman requires bounding the predictable quadratic variation $W_n$ , which is a random quantity. In many applications, you bound $W_n$ by a deterministic quantity $\sigma^2$ using problem-specific arguments. If you cannot bound $W_n$ tightly, Freedman's advantage over Azuma is lost.

The Relationship to Hoeffding vs. Bernstein

Azuma-Hoeffding is to Freedman as Hoeffding is to Bernstein. The parallel is exact:

Independent sums	Martingales
Hoeffding (range only)	Azuma-Hoeffding (range only)
Bernstein (range + variance)	Freedman (range + conditional variance)

Azuma-Hoeffding generalizes Hoeffding from independent sums to martingales. Freedman generalizes Bernstein from independent sums to martingales. The proofs follow the same pattern: Hoeffding's lemma for Azuma, Bernstein's moment condition for Freedman.

When to Use Each

Use Azuma-Hoeffding when:

You only know the bounded range of each increment.
The conditional variance is comparable to the square of the bound.
You want a simple, quick bound for a rough estimate.

Use Freedman when:

The conditional variance $\mathbb{E}[d_i^2 \mid \mathcal{F}_{i-1}]$ is much smaller than $c_i^2$ .
You need tight bounds for rare events (importance sampling, bandit algorithms).
You are working in the "small variance" regime where Azuma wastes a factor of $c^2/\sigma^2$ .

Common Confusions

Watch Out

Freedman bounds a joint event

Freedman's inequality as stated bounds $\Pr[M_n \geq t \text{ and } W_n \leq \sigma^2]$ . This is a joint event. To get a bound on $\Pr[M_n \geq t]$ , you need $\Pr[W_n > \sigma^2]$ to be small, and then apply a union bound. Forgetting the $W_n \leq \sigma^2$ condition is a common error.

Watch Out

Azuma-Hoeffding is not just Hoeffding applied to the sum

The martingale differences $d_i$ are not independent. Azuma-Hoeffding is a genuine martingale result. The proof uses Hoeffding's lemma on each conditional increment, then telescopes. You cannot simply apply the independent-sum Hoeffding inequality to correlated increments.

Watch Out

Freedman does not require bounded increments in the same way Azuma does

Azuma requires $|d_i| \leq c_i$ with possibly different bounds per step. Freedman requires a uniform bound $|d_i| \leq R$ for all $i$ . If the bounds $c_i$ vary wildly, Azuma can be more natural to apply (each step gets its own bound), while Freedman requires a single worst-case $R = \max_i c_i$ .

References

Canonical:

Freedman, "On Tail Probabilities for Martingales" (Annals of Probability, 1975)
Azuma, "Weighted Sums of Certain Dependent Random Variables" (Tohoku Math Journal, 1967)

Current:

Boucheron, Lugosi, Massart, Concentration Inequalities (2013), Chapter 3
Wainwright, High-Dimensional Statistics (2019), Chapter 2