McDiarmid's Bounded Differences Inequality

The precise statement

Let X₁, X₂, …, Xₙ be independent random variables, each Xⱼ taking values in a set 𝒳ⱼ, and let f : 𝒳₁ × ⋯ × 𝒳ₙ → ℝ be a (measurable) function. Suppose f satisfies the bounded differences condition: there exist constants c₁,…,cₙ such that for each coordinate j and every pair of inputs x, x′ ∈ ∏ⱼ 𝒳ⱼ that agree in all coordinates except the j-th,

• |f(x₁,…,xⱼ,…,xₙ) − f(x₁,…,xⱼ′,…,xₙ)| ≤ cⱼ.

Then, writing Z = f(X₁,…,Xₙ), for every t > 0:

• P(Z − 𝔼Z ≥ t) ≤ exp(−2t² / ∑ⱼ₌₁ⁿ cⱼ²), and symmetrically P(Z − 𝔼Z ≤ −t) ≤ exp(−2t² / ∑ⱼ cⱼ²).

A union bound gives the two-sided P(|Z − 𝔼Z| ≥ t) ≤ 2·exp(−2t² / ∑ⱼ cⱼ²). No smoothness, convexity, or moment assumption on f is needed — only that flipping one coordinate cannot move f by more than its budget cⱼ. The concentration scale is √(∑ⱼ cⱼ²), often written ‖c‖₂.

The picture: rigidity from bounded sensitivity

Think of f as a machine with n independent dials. The bounded differences condition says: no matter where the other dials sit, turning dial j alone changes the output by at most cⱼ. Individually each dial has limited leverage. The miracle is that independence forbids these small sensitivities from conspiring — they cannot all push the same direction at once with any appreciable probability.

The natural yardstick is the total influence budget ∑ⱼ cⱼ². If all cⱼ = c, this is nc², so the standard deviation scale is c√n while the maximum possible swing of f is nc. The ratio √n / n = 1/√n → 0: the function occupies a vanishingly thin slice of its own range. This is concentration of measure. A Lipschitz-in-Hamming function of many independent inputs is, with overwhelming probability, essentially constant — equal to its mean up to O(‖c‖₂) fluctuations, with a genuine Gaussian tail rather than merely a variance bound.

The mechanism: a Doob martingale plus Azuma

The proof reveals hidden martingale structure. Define the Doob martingale by revealing coordinates one at a time:

• Zⱼ = 𝔼[f(X₁,…,Xₙ) | X₁,…,Xⱼ], so Z₀ = 𝔼f and Zₙ = f.

The increments Dⱼ = Zⱼ − Zⱼ₋₁ form a martingale difference sequence (𝔼[Dⱼ | X₁,…,Xⱼ₋₁] = 0). The bounded differences hypothesis plus independence force each Dⱼ into an interval of length ≤ cⱼ: conditioning on the past, Dⱼ is a function of Xⱼ alone whose range is controlled by cⱼ. Now apply Hoeffding's lemma — a mean-zero variable in an interval of length ℓ has MGF ≤ exp(λ²ℓ²/8) — to each conditional increment, then chain the conditional MGFs:

• 𝔼[e^{λ(Zₙ−Z₀)}] ≤ ∏ⱼ exp(λ²cⱼ²/8) = exp(λ²∑ⱼcⱼ²/8).

Markov's inequality on e^{λ(Z−𝔼Z)} and optimizing λ = 4t/∑ⱼcⱼ² yields the exponent −2t²/∑ⱼcⱼ². This is exactly the Azuma-Hoeffding inequality applied to the Doob martingale; McDiarmid's contribution was recognizing the bounded-differences hypothesis as the clean, checkable condition that supplies the increment bounds.

Worked example: bin occupancy and the longest common subsequence

Balls in bins. Throw n balls independently into m bins and let f = number of empty bins. Here Xⱼ ∈ {1,…,m} is the destination of ball j, and moving one ball changes the empty-bin count by at most 1, so cⱼ = 1 for all j and ∑ⱼcⱼ² = n. McDiarmid gives P(|f − 𝔼f| ≥ t) ≤ 2·exp(−2t²/n). The mean is 𝔼f = m(1 − 1/m)ⁿ; the number of empty bins is concentrated within ~√n of it — a fact that would be painful to prove by directly computing the variance and higher moments of this dependent count.

Longest common subsequence. For two random strings of length n over an alphabet, LCS changes by at most 1 when a single character is altered, so again cⱼ = 1 and LCS concentrates within O(√n) of its (unknown!) mean. This is the classic illustration of McDiarmid's power: you get concentration without ever knowing 𝔼f. The inequality certifies rigidity purely from the sensitivity structure.

Why the hypotheses matter — and what breaks

Independence is essential. Drop it and the bound is false. Let X₁ = X₂ = ⋯ = Xₙ be a single fair ±1 coin copied n times, and f = ∑ⱼ Xⱼ. Each cⱼ = 2 (flipping coordinate j moves the sum by 2), so ∑ⱼcⱼ² = 4n and McDiarmid would predict fluctuations O(√n). But f = ±n with probability 1/2 each: fluctuations are order n, not √n. The perfectly correlated coordinates let the sensitivities align — exactly what independence forbids.

Bounded differences is essential. If a single coordinate can swing f arbitrarily (cⱼ = ∞), no sub-Gaussian tail can hold; take f = X₁ with X₁ heavy-tailed. The constants cⱼ must be genuine worst-case bounds over all values of the other coordinates.

Connections. McDiarmid specializes to Hoeffding's inequality (f = ∑Xⱼ, cⱼ = bⱼ−aⱼ) and generalizes the Azuma-Hoeffding martingale bound to the natural functional setting. Variance-aware refinements (McDiarmid's later 1998 survey, Bousquet, Boucheron-Lugosi-Massart) replace ∑cⱼ² with a variance proxy to beat the crude √(∑cⱼ²) scale when f is usually far less sensitive than its worst case.

Applications and significance

McDiarmid's inequality is the default tool whenever a quantity of interest is a mildly-sensitive function of many independent pieces:

• Statistical learning theory. Uniform bounds on the gap between empirical and true risk hinge on the fact that sup over a hypothesis class of the empirical-process error has bounded differences (swapping one training point of n changes it by 1/n). This yields generalization bounds and underlies Rademacher complexity arguments — the backbone of PAC learning guarantees.
• Random graphs & combinatorics. Chromatic number, clique number, and component sizes of G(n,p) are Lipschitz in the edge/vertex indicators, so they concentrate — a cornerstone technique in the probabilistic method (Alon-Spencer).
• Randomized algorithms. Runtime and cost of hashing, load balancing, and random projections concentrate sharply.
• High-dimensional geometry. Lipschitz functions on the discrete cube concentrate, the combinatorial analogue of Lévy's concentration on the sphere.

Its significance is conceptual as much as technical: it converts a local smoothness property (coordinate-wise Lipschitzness) into a global probabilistic near-constancy, and does so with a proof short enough to teach in one lecture.

McDiarmid's inequality against neighboring concentration bounds

Inequality	Hypothesis on the random object	One-sided tail bound	When to reach for it
Hoeffding (1963)	f = ∑ⱼ Xⱼ, sum of independent Xⱼ ∈ [aⱼ, bⱼ]	exp(−2t² / ∑ⱼ (bⱼ−aⱼ)²)	The function is literally a bounded sum
McDiarmid (1989)	Independent Xⱼ, any f with |Δⱼf| ≤ cⱼ	exp(−2t² / ∑ⱼ cⱼ²)	Nonlinear/combinatorial f of independent inputs
Azuma-Hoeffding (1967)	Martingale with bounded increments |Dⱼ| ≤ cⱼ	exp(−t² / (2∑ⱼ cⱼ²))	You already have a martingale (dependent data)
Bernstein / Bennett	Bounded, plus variance control σ²	exp(−t² / (2σ² + 2ct/3))	Variance ≪ range; sharper for small t