Proving McDiarmid with Doob Martingales

Why Reveal the Inputs One at a Time?

A function of many independent observations can be concentrated even when it is not a sum. The useful condition is that changing any one input cannot change the function by very much. To turn that condition into a tail bound, reveal the inputs successively and track how the conditional expectation of the function changes. Those successive changes form a Doob martingale.

The key point is a bound on the range of each martingale increment, not necessarily a bound on its absolute value by half that range. A centered variable can have an asymmetric interval of possible values. The exponential argument below uses interval length directly, which is what makes the proof work in that generality.

Setup and Bounded Coordinate Changes

Definition: Let $X_1,\ldots,X_n$ be independent random elements, and let $f(X_1,\ldots,X_n)$ be a bounded measurable real-valued function. We say $f$ has bounded coordinate differences $c_1,\ldots,c_n$, where each $c_i\geq 0$, if for every two input vectors $x,x'$ that agree except possibly in coordinate $i$, $$ |f(x)-f(x')|\leq c_i. $$

The constants may differ across coordinates. Boundedness of $f$ ensures its expectation and all conditional expectations below are finite. Independence is essential to the argument: after the first $i$ inputs are revealed, the unrevealed inputs retain their original joint distribution.

Define $M_i=E[f(X_1,\ldots,X_n)\mid X_1,\ldots,X_i]$ for $i=1,\ldots,n$, and $M_0=E[f(X_1,\ldots,X_n)]$. Then $M_n=f(X_1,\ldots,X_n)$ and $E[M_i\mid X_1,\ldots,X_{i-1}]=M_{i-1}$. The increments $D_i=M_i-M_{i-1}$ therefore have conditional mean zero. We will show that, given the first $i-1$ inputs, the possible values of $D_i$ lie in an interval of length at most $c_i$.

Worked Example: Revealing Inputs for an “At Least One” Function

Let $X_1,X_2$ be independent Bernoulli random variables with success probability $1/2$, and let $f(X_1,X_2)=\mathbf{1}\{X_1=1\text{ or }X_2=1\}$. The function changes by at most $1$ when either input changes, so take $c_1=c_2=1$.

The function equals zero only when both inputs are zero. Thus $M_0=E[f]=1-P(X_1=0,X_2=0)=1-1/4=3/4$. After revealing $X_1$, $M_1=1$ if $X_1=1$, and $M_1=1/2$ if $X_1=0$. Hence $D_1=M_1-M_0$ is $1/4$ when $X_1=1$ and $-1/4$ when $X_1=0$; its range has length $1/2$, at most $c_1$.

If $X_1=1$, then $M_2=f=1$ regardless of $X_2$, so $D_2=0$. If $X_1=0$, then $M_1=1/2$ and $M_2=X_2$; consequently $D_2=-1/2$ for $X_2=0$ and $D_2=1/2$ for $X_2=1$. Its conditional range has length $1$, exactly $c_2$. In both cases the conditional mean of $D_2$ is zero.

The Exponential Bound for a Bounded Range

We need a fact about a centered random variable whose possible values lie in an interval. The interval need not be centered at zero.

Lemma (Hoeffding’s lemma): If $W$ is a bounded random variable taking values in an interval $[a,b]$, then for every real $\lambda$, $$ E\!\left[\exp\{\lambda(W-E[W])\}\right] \leq \exp\!\left(\frac{\lambda^2(b-a)^2}{8}\right). $$

Proof. Write $V=W-E[W]$, and define $h(\lambda)=\log E[\exp(\lambda V)]$. Since $V$ is bounded, the expectation can be differentiated twice for every $\lambda$; boundedness supplies an integrable bound for the derivatives on every bounded interval of $\lambda$. Direct differentiation gives $h(0)=0$, $h'(0)=E[V]=0$, and

h''(\lambda)=\operatorname{Var}_{\lambda}(V),

where $\operatorname{Var}_{\lambda}$ denotes variance under the probability distribution tilted by the weight proportional to $\exp(\lambda V)$. This tilted distribution still has support in an interval of length $b-a$. For any random variable $U$ supported on $[a,b]$, its variance is at most $(b-a)^2/4$: with $m=(a+b)/2$,

\operatorname{Var}(U)=\min_{r\in\mathbb{R}}E[(U-r)^2] \leq E[(U-m)^2]\leq \frac{(b-a)^2}{4}.

Therefore $h''(\lambda)\leq (b-a)^2/4$. For $\lambda\geq0$, integrating twice from zero gives $h(\lambda)=\int_0^\lambda(\lambda-s)h''(s)\,ds\leq \lambda^2(b-a)^2/8$. For $\lambda<0$, the corresponding integral is $h(\lambda)=\int_\lambda^0(s-\lambda)h''(s)\,ds\leq \lambda^2(b-a)^2/8$. Exponentiating proves the lemma. $\square$

Why the Doob Increments Have Short Ranges

Fix the first $i-1$ inputs. For a possible value $x_i$, the conditional expectation $M_i$ averages $f$ over the as-yet-unrevealed inputs $X_{i+1},\ldots,X_n$, with $X_1,\ldots,X_i$ fixed. Compare two possible values $x_i$ and $x_i'$, using the same values of all later inputs in both averages. The coordinate-difference assumption bounds the difference between the corresponding values of $f$ by $c_i$. Integrating over the same distribution of later inputs preserves that bound. Thus the possible values of $M_i$, conditional on the first $i-1$ inputs, lie in an interval of length at most $c_i$.

Subtracting $M_{i-1}$, which is the conditional mean of $M_i$, shifts this interval but does not change its length. Hence $D_i$, conditionally on the first $i-1$ inputs, is centered and lies in an interval of length at most $c_i$. Applying Hoeffding’s lemma conditionally yields

E[\exp(\lambda D_i)\mid X_1,\ldots,X_{i-1}] \leq \exp\!\left(\frac{\lambda^2c_i^2}{8}\right).

McDiarmid’s Inequality from the Martingale

Theorem (McDiarmid’s inequality): Under the independence, boundedness, measurability, and bounded coordinate difference assumptions above, for every $t>0$, $$ P\!\left(f(X_1,\ldots,X_n)-E[f(X_1,\ldots,X_n)]\geq t\right) \leq \exp\!\left(-\frac{2t^2}{\sum_{i=1}^n c_i^2}\right), $$ when $\sum_{i=1}^n c_i^2>0$. Consequently, $$ P\!\left(\left|f(X_1,\ldots,X_n)-E[f(X_1,\ldots,X_n)]\right|\geq t\right) \leq 2\exp\!\left(-\frac{2t^2}{\sum_{i=1}^n c_i^2}\right). $$

Proof. Since $f-E[f]=M_n-M_0=\sum_{i=1}^nD_i$, iterated conditional expectation and the conditional exponential bound give, for $\lambda>0$,

E\!\left[\exp\!\left(\lambda\sum_{i=1}^nD_i\right)\right] \leq \exp\!\left(\frac{\lambda^2}{8}\sum_{i=1}^n c_i^2\right).

Indeed, condition first on $X_1,\ldots,X_{n-1}$, apply the bound for $D_n$, and then repeat for $D_{n-1},\ldots,D_1$. Markov’s inequality now implies

P\!\left(\sum_{i=1}^nD_i\geq t\right) \leq \exp\!\left(-\lambda t+\frac{\lambda^2}{8}\sum_{i=1}^n c_i^2\right).

Set $C=\sum_{i=1}^n c_i^2>0$. The exponent is minimized over $\lambda>0$ at $\lambda=4t/C$, giving $-4t^2/C+2t^2/C=-2t^2/C$. This proves the upper-tail bound. Apply the same argument to $-f$, which has the same coordinate-difference bounds, to obtain the lower-tail bound; adding the two probabilities proves the two-sided bound. If $C=0$, every coordinate difference is zero, so $f$ is constant on its product domain and the deviation probability is zero. $\square$

Worked Example: A Weighted Sum of Two Bernoulli Inputs

Let $X_1\sim\operatorname{Bernoulli}(1/4)$ and $X_2\sim\operatorname{Bernoulli}(3/4)$ be independent, and define $f=2X_1+X_2$. Changing $X_1$ changes $f$ by at most $2$; changing $X_2$ changes it by at most $1$. Thus $c_1=2$, $c_2=1$, and $C=2^2+1^2=5$.

The expectation is $E[f]=2(1/4)+3/4=5/4$. After revealing $X_1$, $M_1=2X_1+E[X_2]=2X_1+3/4$. Therefore $D_1=M_1-M_0=2(X_1-1/4)$, which is $3/2$ if $X_1=1$ and $-1/2$ if $X_1=0$. The range length is $2$. The second increment is $D_2=X_2-3/4$, equal to $1/4$ or $-3/4$, with range length $1$. These are the coordinate bounds used in the theorem.

For a deviation of $t=1$, the one-sided guarantee is $$ P(f-E[f]\geq 1)\leq \exp(-2/5)\approx 0.6703. $$ For a direct check, the possible values of $f$ are $0,1,2,3$, so $f-E[f]\geq1$ occurs only when $f=3$, which requires both inputs to equal $1$. Its probability is $(1/4)(3/4)=3/16=0.1875$, below the stated upper bound.

Worked Example: Centering Does Not Halve the Range

Let $Z$ equal $10$ with probability $0.9$ and $11$ with probability $0.1$. Its mean is $E[Z]=10(0.9)+11(0.1)=10.1$. Thus $Z-E[Z]$ equals $-0.1$ with probability $0.9$ and $0.9$ with probability $0.1$. The centered values lie in $[10-10.1,11-10.1]=[-0.1,0.9]$, an interval of length $1$. Their largest absolute value is $0.9$, not $1/2$.

Hoeffding’s lemma applies using the interval length $1$, and gives, for every real $\lambda$, $$ E[\exp\{\lambda(Z-E[Z])\}] =0.9e^{-0.1\lambda}+0.1e^{0.9\lambda} \leq e^{\lambda^2/8}. $$ The bound depends on the length of the centered interval, not on claiming that all centered values have absolute value at most half its length.

Common Pitfall and Why the Proof Matters

A tempting but incorrect step is to say that a variable in an interval of length $c_i$, after centering, must lie between $-c_i/2$ and $c_i/2$. Centering subtracts the mean; unless the mean is the midpoint of the interval, that conclusion does not follow. The correct statement is that centering shifts the interval while preserving its length. Hoeffding’s lemma controls the exponential moment using that length, so no symmetric absolute bound is needed.

The proof also explains why the sum of squared coordinate bounds appears: each newly revealed input contributes an increment with an exponential cost proportional to $c_i^2$, and these costs add when the conditional bounds are iterated. This martingale route is useful for functions that are not sums, provided changing one input has a controlled effect. The bound can be conservative when the coordinate bounds are loose, but its assumptions and constants are transparent.

Check Your Understanding

Answer these questions by identifying the range and conditional-expectation steps in the proof.

Why does subtracting $M_{i-1}$ from $M_i$ preserve the length of the conditional range?
If $D_i$ has conditional mean zero and lies in an interval of length $c_i$, what conditional exponential-moment bound follows from Hoeffding’s lemma?
For coordinate bounds $c_1=1$, $c_2=2$, and $c_3=2$, what is the exponent in the one-sided McDiarmid bound at deviation $t$?
In the weighted Bernoulli example, why is $D_1$'s range length $2$, even though its possible values are $-1/2$ and $3/2$?
What is the error in asserting that a centered variable in an interval of length $c$ must have absolute value at most $c/2$?