McDiarmid's Bounded Differences Inequality

Hoeffding's inequality tells you that a sum of independent bounded random variables concentrates tightly around its mean. But most quantities a quant actually cares about — a cross-validation error, a portfolio statistic computed from many trades, a test statistic built from a whole dataset — aren't simple sums; they're some arbitrary function of many independent inputs. McDiarmid's inequality extends the same concentration idea to any such function, as long as it satisfies one condition: changing just one of its many independent inputs, while holding all the others fixed, can never move the output by more than some bounded amount $c_i$.

$$\Pr\big(|f(X_1,\dots,X_n) - \mathbb{E}[f]| \ge t\big) \le 2\exp\!\left(\frac{-2t^2}{\sum_i c_i^2}\right)$$

In words: the probability that the function's value strays far from its average shrinks exponentially fast as the deviation $t$ grows, and the rate of that shrinkage depends only on how sensitive the function is to each individual input, not on how complicated the function otherwise is.

A concrete use: suppose a model's out-of-sample error is computed by leave-one-out cross-validation across $n = 1{,}000$ independent samples, and removing any single sample can change the reported error by at most $c = 1/n$. McDiarmid's inequality then guarantees this cross-validation estimate concentrates tightly around its expected value, with deviations larger than a small threshold becoming exponentially unlikely as $n$ grows — exactly the kind of guarantee that justifies trusting a single cross-validation run rather than re-running it many times.