The Azuma-Hoeffding Inequality: Concentration for Martingales

The precise statement

Let (Ω, ℱ, ℙ) carry a filtration ℱ₀ ⊆ ℱ₁ ⊆ … ⊆ ℱₙ, and let (Mₖ)ₖ₌₀ⁿ be a martingale adapted to it: each Mₖ is ℱₖ-measurable, integrable, and 𝔼[Mₖ | ℱₖ₋₁] = Mₖ₋₁ almost surely. Suppose the increments Dₖ := Mₖ − Mₖ₋₁ are bounded: there exist constants cₖ > 0 with |Dₖ| ≤ cₖ a.s. for each k. Then for every t > 0,

• ℙ(Mₙ − M₀ ≥ t) ≤ exp( −t² / (2∑ₖ₌₁ⁿ cₖ²) ),
• ℙ(Mₙ − M₀ ≤ −t) ≤ exp( −t² / (2∑ₖ₌₁ⁿ cₖ²) ), and hence
• ℙ(|Mₙ − M₀| ≥ t) ≤ 2·exp( −t² / (2∑ₖ₌₁ⁿ cₖ²) ).

A sharper hypothesis suffices: it is enough that each increment lie in an interval of length cₖ, i.e. Aₖ ≤ Dₖ ≤ Aₖ + cₖ where Aₖ is ℱₖ₋₁-measurable. The same bound holds with cₖ² replaced by cₖ²/4, matching Hoeffding's factor. The one-sided version needs only a supermartingale (𝔼[Mₖ | ℱₖ₋₁] ≤ Mₖ₋₁).

Intuition: bounded steps can't add up to a big jump

Picture a random walk whose step sizes are capped by cₖ but whose direction and distribution can be chosen adversarially at each stage, using all the history so far. The martingale condition forces each step to have conditional mean zero: on average the walk goes nowhere. The only freedom left to an adversary is the shape of each step's distribution.

Hoeffding's lemma pins down the worst case: among all mean-zero variables bounded by cₖ (i.e. confined to [−cₖ, cₖ]), the one whose moment generating function grows fastest is the two-point ±cₖ coin. So each step contributes at most as much "spreading power" as a fair ±cₖ coin flip. Summing n such fair-coin steps gives a distribution with variance ∑cₖ² that is sub-Gaussian, and sub-Gaussian tails are exactly e^(−t²/2σ²) with σ² = ∑cₖ². The theorem says you never do worse than this worst case, so a chain of bounded, unpredictable steps concentrates just as tightly as a Gaussian of the matching variance — even though the increments may be wildly dependent.

The mechanism of the proof

The engine is the Chernoff / exponential-moment method combined with the martingale's tower property. Fix λ > 0. By Markov's inequality applied to e^(λ(Mₙ−M₀)),

ℙ(Mₙ − M₀ ≥ t) ≤ e^(−λt) · 𝔼[ e^(λ(Mₙ−M₀)) ].

Now peel off the last increment by conditioning on ℱₙ₋₁ and using the tower property:

𝔼[ e^(λ(Mₙ−M₀)) ] = 𝔼[ e^(λ(Mₙ₋₁−M₀)) · 𝔼[ e^(λDₙ) | ℱₙ₋₁ ] ].

Here is the crux — Hoeffding's lemma: for any random variable D with 𝔼[D | ℱₙ₋₁] = 0 and |D| ≤ cₙ, we have 𝔼[e^(λD) | ℱₙ₋₁] ≤ e^(λ²cₙ²/2) almost surely. The conditional mean-zero property (martingale!) is exactly what makes this available. Substituting and iterating the peel-off down to M₀ gives 𝔼[e^(λ(Mₙ−M₀))] ≤ exp(λ²∑cₖ²/2). Finally optimize: minimizing e^(−λt)·e^(λ²∑cₖ²/2) over λ > 0 gives λ* = t/∑cₖ², yielding exp(−t²/(2∑cₖ²)). The two-point extremal case in Hoeffding's lemma is where all the tightness lives.

Worked example: the Doob martingale and McDiarmid's inequality

Let X₁, …, Xₙ be independent random variables and f a function such that changing one coordinate moves f by at most cₖ: |f(x) − f(x′)| ≤ cₖ whenever x, x′ differ only in coordinate k (the bounded differences property). Build the Doob martingale Mₖ = 𝔼[ f(X₁,…,Xₙ) | X₁,…,Xₖ ], so M₀ = 𝔼[f] and Mₙ = f. Independence plus bounded differences give |Mₖ − Mₖ₋₁| ≤ cₖ, so Azuma-Hoeffding applies and yields

ℙ( |f(X) − 𝔼f| ≥ t ) ≤ 2·exp( −2t² / ∑cₖ² ),

which is McDiarmid's inequality (the factor 2 in the exponent comes from the interval-length refinement). Concrete instance: in a random graph G(n, p), the chromatic number χ(G) changes by at most 1 when you resample all edges at a single vertex, so with n vertices, cₖ = 1 and χ concentrates within O(√(n log n)) of its mean — a landmark result of Shamir and Spencer proved exactly this way.

Why the hypotheses matter

Bounded increments are essential. Drop them and the Gaussian tail fails: let Dₖ be mean-zero but heavy-tailed (say a symmetrized variable with only a few finite moments). Then Mₙ is still a martingale, but its tail is only polynomial, not exponential — the moment generating function 𝔼[e^(λD)] can be infinite, so Hoeffding's lemma has nothing to say and the whole Chernoff argument collapses.

The martingale (mean-zero-increment) structure is essential. If 𝔼[Dₖ | ℱₖ₋₁] = μ ≠ 0, the walk drifts; Mₙ − M₀ concentrates around nμ, not 0, and the centered bound is simply false. Hoeffding's lemma needs the conditional mean to vanish.

• For a supermartingale (negative drift), the upper tail bound survives — drift only helps you not exceed t.
• The constant is not improvable in general: for ±cₖ coins it matches the central limit theorem's Gaussian, so Azuma-Hoeffding is asymptotically tight.
• When you additionally control the conditional variances, Freedman's inequality (a Bernstein-type martingale bound) beats it in the low-variance regime.

Why it matters and what it unlocks

Azuma-Hoeffding is the bridge from Hoeffding's independent-sum bound to the dependent world, and it underwrites a huge swath of modern probability, combinatorics, and computer science:

• The probabilistic method: concentration of graph parameters (chromatic number, longest increasing subsequence, isoperimetry) via Doob martingales — the foundation of the martingale method in combinatorics (Alon, Spencer).
• Statistical learning theory: generalization bounds, Rademacher complexity, and stability arguments all invoke McDiarmid, i.e. Azuma-Hoeffding in disguise.
• Randomized algorithms & balls-in-bins: tight high-probability runtime and load-balancing guarantees.
• Stochastic optimization and bandits: confidence sequences and regret bounds for adaptively collected (hence dependent) data, where independence-based Hoeffding is unavailable but the martingale structure survives.

Historically it descends from Wassily Hoeffding's 1963 independent-variable inequality and was extended to martingales by Kazuoki Azuma in 1967 (with roots in Sergei Bernstein's work). Its philosophical payoff: dependence is harmless for concentration as long as no single step can move the outcome much.

Azuma-Hoeffding compared with neighboring concentration inequalities

Inequality	Structure required	Bound on ℙ(deviation ≥ t)	Relationship
Hoeffding (1963)	Independent Xₖ ∈ [aₖ, bₖ]	exp(−2t² / ∑(bₖ−aₖ)²)	Special case: partial sums of independent bounded vars form a martingale
Azuma-Hoeffding (1967)	Martingale, |Mₖ − Mₖ₋₁| ≤ cₖ a.s.	exp(−t² / (2∑cₖ²))	The general result; increments may depend on the past
McDiarmid (1989)	f with bounded differences cₖ, X independent	exp(−2t² / ∑cₖ²)	Corollary via the Doob martingale of f(X₁,…,Xₙ)
Bernstein/Freedman	Martingale + variance control	exp(−t² / (2(V + ct/3)))	Sharper when total conditional variance V ≪ ∑cₖ²