The Doob Martingale Proof of Bounded Differences

From Independent Inputs to a Martingale

A function of independent observations need not be a sum. It might be a maximum, a product, or a statistic built from many interacting inputs. The bounded-difference condition handles such functions by asking how much the output can change when just one input is replaced. The proof then reveals the inputs one at a time and tracks the successive changes in conditional expectation.

Those successive changes form a Doob martingale. Although its increments are generally not independent, the bounded-difference condition controls their conditional ranges. Hoeffding’s lemma can be applied conditionally at each step, and iterating the resulting moment-generating-function bounds gives McDiarmid’s inequality.

Definition: Let $X_1,\ldots,X_n$ be independent random elements, and let $g$ be a bounded measurable real-valued function of their values. Write $Z=g(X_1,\ldots,X_n)$, and define $\mathcal{F}_i=\sigma(X_1,\ldots,X_i)$, with $\mathcal{F}_0$ the trivial sigma-field. The Doob martingale of $Z$ with respect to this sequence is $M_i=E[Z\mid\mathcal{F}_i]$, for $i=0,\ldots,n$. Its increments are $D_i=M_i-M_{i-1}$, for $i=1,\ldots,n$.

The conditional-expectation definition gives $M_0=E[Z]$ and $M_n=Z$ almost surely. Also, $E[D_i\mid\mathcal{F}_{i-1}]=0$. Thus the increments satisfy $Z-E[Z]=\sum_{i=1}^n D_i$. The key task is to bound the range of $D_i$, conditional on the inputs already revealed.

Bounded Differences and Conditional Ranges

Bounded-difference condition: For constants $c_1,\ldots,c_n\geq 0$, the function $g$ satisfies this condition if, for every pair of input vectors $x,x'$ that differ only in coordinate $i$, $$ |g(x)-g(x')|\leq c_i. $$ The value $c_i$ bounds the change in $g$ when its $i$th input alone is replaced.

Here is the link between this condition and the martingale increments. Given the first $i-1$ inputs and a candidate value $x_i$ for the next one, average $g$ over the remaining inputs:

h_i(x_1,\ldots,x_i) = \int g(x_1,\ldots,x_i,x_{i+1},\ldots,x_n) \,d\mu_{i+1}(x_{i+1})\cdots d\mu_n(x_n),

where $\mu_j$ is the distribution of $X_j$; for $i=n$, this is just $g(x_1,\ldots,x_n)$. The integral exists because $g$ is bounded and measurable. Independence ensures that, given the first $i$ inputs, the unrevealed inputs have their original product distribution. Consequently $M_i=h_i(X_1,\ldots,X_i)$ almost surely.

If $x_i$ and $x_i'$ are two possible values of the $i$th input, the vectors inside the integral differ only in coordinate $i$. The bounded-difference condition therefore implies

|h_i(x_1,\ldots,x_i)-h_i(x_1,\ldots,x_{i-1},x_i')| \leq c_i.

So, with the past fixed, $M_i$ ranges over an interval of length at most $c_i$ as $X_i$ varies. Subtracting $M_{i-1}$, which is fixed given that past, shifts this interval but does not change its length. Thus $D_i$, conditionally on $\mathcal{F}_{i-1}$, lies in an interval of length at most $c_i$, and its conditional mean is zero.

McDiarmid’s Inequality: The Doob-Martingale Proof

We use Hoeffding’s lemma in its centered form: if a random variable $W$ lies almost surely in an interval of length $c$, then, for every real $\lambda$,

E\!\left[e^{\lambda(W-E[W])}\right]\leq \exp\!\left(\frac{\lambda^2c^2}{8}\right).

The same bound holds conditionally when the interval and mean are interpreted given a sigma-field. Applying it to $D_i$ conditional on $\mathcal{F}_{i-1}$ gives

E[e^{\lambda D_i}\mid\mathcal{F}_{i-1}] \leq \exp\!\left(\frac{\lambda^2c_i^2}{8}\right).

Theorem (McDiarmid’s inequality): Let $X_1,\ldots,X_n$ be independent random elements and let $g$ be bounded and measurable, satisfying the bounded-difference condition with constants $c_1,\ldots,c_n$. Set $C=\sum_{i=1}^n c_i^2$. If $C>0$, then, for every $t>0$, $$ P\bigl(g(X_1,\ldots,X_n)-E[g(X_1,\ldots,X_n)]\geq t\bigr) \leq \exp\!\left(-\frac{2t^2}{C}\right), $$ and $$ P\bigl(|g(X_1,\ldots,X_n)-E[g(X_1,\ldots,X_n)]|\geq t\bigr) \leq 2\exp\!\left(-\frac{2t^2}{C}\right). $$

Bound the moment-generating function.
Since $Z-E[Z]=\sum_{i=1}^nD_i$, condition on $\mathcal{F}_{n-1}$ and apply the conditional Hoeffding bound to $D_n$. Repeating this step for $D_{n-1},\ldots,D_1$ gives $E[e^{\lambda(Z-E[Z])}]\leq\exp(\lambda^2C/8)$.

Apply Markov’s inequality.
For $\lambda>0$, $P(Z-E[Z]\geq t)\leq e^{-\lambda t}E[e^{\lambda(Z-E[Z])}]\leq\exp(-\lambda t+\lambda^2C/8)$.

Optimize and include the lower tail.
The exponent is minimized at $\lambda=4t/C$, giving the upper-tail bound. Apply the same argument to $-Z$ for the lower tail and add the two probabilities.

For completeness, the moment-generating-function iteration in Step 1 follows directly from conditional expectation. If $S_{i-1}=\sum_{j=1}^{i-1}D_j$, then $S_{i-1}$ is $\mathcal{F}_{i-1}$-measurable, so

E[e^{\lambda(S_{i-1}+D_i)}] = E\!\left[e^{\lambda S_{i-1}}E[e^{\lambda D_i}\mid\mathcal{F}_{i-1}]\right] \leq e^{\lambda^2c_i^2/8}E[e^{\lambda S_{i-1}}].

Iterating from $i=1$ to $n$ yields the stated bound. In the tail calculation, substituting $\lambda=4t/C$ gives $-\lambda t+\lambda^2C/8=-2t^2/C$. If $C=0$, every coordinate has zero allowed change, so $g$ is constant on its product domain and the centered deviation is zero; the tail probability is then zero for $t>0$. This completes the proof. $\square$

Worked Applications

Worked Example: A Bernoulli Sample Proportion

Let $X_1,\ldots,X_{100}$ be independent Bernoulli random variables with success probability $1/2$, and let $Z=100^{-1}\sum_{i=1}^{100}X_i$. Replacing one input changes the sum by at most $1$, so it changes $Z$ by at most $c_i=1/100$. Therefore

$C=100(1/100)^2=1/100$, and $E[Z]=1/2$. For a deviation of $t=0.1$, McDiarmid’s inequality gives

P(|Z-1/2|\geq 0.1) \leq 2\exp\!\left(-\frac{2(0.1)^2}{1/100}\right) =2e^{-2} \approx 0.2707.

For the upper tail alone, the bound is $e^{-2}\approx 0.1353$. This example recovers a familiar independent-sum concentration bound, now expressed through the successive conditional expectations of the sample proportion.

Worked Example: An Empirical CDF at a Fixed Point

Let $X_1,\ldots,X_{40}$ be independent Uniform$(0,1)$ observations. At the fixed point $a=0.3$, the empirical CDF is $F_{40}(a)=40^{-1}\sum_{i=1}^{40}\mathbf{1}\{X_i\leq a\}$. Each indicator has mean $0.3$, so $E[F_{40}(a)]=0.3$. Replacing one observation changes at most one indicator and hence changes $F_{40}(a)$ by at most $1/40$. Thus

$C=40(1/40)^2=1/40$. For $t=0.15$, the two-sided bound is

P(|F_{40}(0.3)-0.3|\geq 0.15) \leq 2\exp\!\left(-\frac{2(0.15)^2}{1/40}\right) =2e^{-1.8} \approx 0.3306.

The argument applies to this fixed point without requiring the statistic to be a sum of the original observations themselves: it is enough that it is a function of independent inputs with bounded changes.

Worked Example: A Product of Two Bernoulli Variables

Let $X_1,X_2$ be independent Bernoulli$(1/2)$ variables and set $Z=X_1X_2$. The expectation is $E[Z]=1/4$. Replacing either input changes the product by at most $1$, so take $c_1=c_2=1$ and $C=2$. The one-sided inequality at $t=0.5$ gives

P(Z-1/4\geq 0.5) \leq \exp\!\left(-\frac{2(0.5)^2}{2}\right) =e^{-0.25} \approx 0.7788.

The event on the left is exactly $\{X_1=X_2=1\}$, because $Z$ is either $0$ or $1$, and only $Z=1$ has $Z-1/4\geq 0.5$. Its actual probability is $1/4$, confirming the bound. The Doob martingale makes the successive revelation explicit: $M_0=1/4$, $M_1=X_1/2$, and $M_2=X_1X_2$. Hence $D_1=X_1/2-1/4$, while $D_2=X_1X_2-X_1/2$. Given $X_1=0$, $D_2=0$; given $X_1=1$, $D_2=X_2-1/2$, which has conditional mean zero.

Why the Martingale View Matters

The proof works because each increment is centered conditionally on the past and has a controlled conditional range. Independence is used to ensure that, after revealing the first $i$ inputs, the unrevealed inputs still follow their original product distribution. That lets us average over the future and carry the one-coordinate sensitivity bound into the conditional-expectation martingale.

The martingale increments are not generally independent. The proof does not need them to be: it bounds each increment’s conditional moment-generating function and iterates those bounds. This is why the method covers nonlinear functions of independent inputs, rather than only sums of independent random variables.

Common Pitfall

Using the wrong interval length. If $D_i$ has conditional mean zero and lies in an interval of length $c_i$, Hoeffding’s lemma uses $c_i$, not $2c_i$. Centering shifts the interval but does not double its length.
Assuming the increments are independent. They need not be. The valid step is the conditional moment-generating-function bound given $\mathcal{F}_{i-1}$, followed by iterated conditional expectation.
Applying the result to an unverified function. The bound requires checking that replacing input $i$ changes the function by at most $c_i$, uniformly over the other inputs.

Key takeaway: Reveal independent inputs one at a time, form the Doob martingale of the statistic, and use the coordinatewise change bound to control each increment’s conditional range. Hoeffding’s lemma then yields McDiarmid’s tail exponent $2t^2/\sum_i c_i^2$.

Check Your Understanding

Try these questions using the conditional-range argument and the theorem.

Why does conditioning on $\mathcal{F}_{i-1}$ leave the unrevealed inputs with their original distributions?
If $D_i$ lies conditionally in an interval of length $c_i$, what is the corresponding conditional moment-generating-function bound?
For $Z=n^{-1}\sum_{i=1}^n X_i$, where changing one $X_i$ changes the sum by at most $1$, identify $c_i$ and $\sum_i c_i^2$.
Why does the proof not require the Doob martingale increments to be independent?
What happens to the tail probability bound when every $c_i=0$?