Bounded differences and McDiarmid's inequality

Let independent random elements X₁ through X_n take values in specified measurable spaces, and let f be a measurable integrable real function on their product. Suppose replacing coordinate i while holding all others fixed changes f by at most a deterministic c_i. The condition is uniform over the product domain, or over fixed full-measure coordinate supports where the argument remains valid. It is not merely a bound on derivatives observed at the sampled inputs. Discrete data, strings, or category labels require no differential structure.

McDiarmid bounds the upper deviation f(X)−Ef(X) by exp(−2t²/Σc_i²), with the same lower-tail bound and a factor two for an absolute deviation. The zero-total-sensitivity case is deterministic on the relevant product support. The center is the expectation of f, which may differ from the population quantity one wants to estimate. For a biased estimator this inequality controls fluctuation around its own mean, not its bias; a separate calculation is needed to connect that mean with an external target.

Reveal coordinates in order and define M_i as the conditional expectation of f given the first i inputs. The difference M_i−M_(i−1) has conditional mean zero. For a fixed past, the conditional expectation over the unrevealed independent inputs is a function of the new coordinate whose range has width at most c_i. Subtracting its conditional mean preserves that width. Conditional Hoeffding's lemma then bounds the mgf of each difference, and successive conditioning gives the exponential bound for the final sum.

This is stronger than merely proving the absolute difference is at most c_i and inserting it into a symmetric range of width 2c_i, which would lose a factor four in the exponent. The proof controls the actual conditional range width. It also explains why independence cannot be discarded: with dependent inputs, revealing one coordinate may change the conditional law of all unrevealed coordinates. The conditional expectation can then move much more than the effect of one formal replacement in f's argument.

Consider the number of distinct categories in an independent sample from a countable alphabet. Replacing one observation can remove at most one old category and introduce at most one new one, but the net number changes by at most one. Dividing by n gives sensitivity 1/n. This statistic is nonlinear, and its expected value depends on the category distribution; nevertheless its fluctuation satisfies the same scale as a bounded sample average. No identical-distribution assumption is needed for the sensitivity argument itself.

For a counterexample, let every X_i equal the same Bernoulli variable B and take f to be their average. As a formal product-space function it has sensitivity 1/n, yet f(X)=B has no improvement with n. Independent-copy concentration would falsely predict exponentially decreasing error. Conditioning can recover a valid theorem only if it establishes the necessary conditional increment ranges or some other appropriate dependence structure. The phrase conditionally independent must specify the conditioning information, and conditional fluctuation around a random conditional mean does not automatically control fluctuation around the unconditional mean.