McDiarmid's Inequality

Bounded differences give concentration. The workhorse of combinatorial probability.

The idea

Theorem (McDiarmid's inequality).

Let $X_1, \ldots, X_n$ be independent, and let $f$ be a real-valued function of all $n$ of them satisfying the bounded differences condition: for each coordinate $i$ there is a constant $c_i$ such that replacing $x_i$ by any other value, with the remaining $n - 1$ coordinates held fixed at any values, moves $f$ by at most $c_i$. Then for every $t > 0$, $\mathbb{P}\big(|f - \mathbb{E}[f]| \geq t\big) \leq 2\exp\!\left(\frac{-2t^{2}}{\sum_{i} c_i^{2}}\right).$

In words: a function of many independent inputs, no one of which can move it much on its own, is very nearly constant.

The inequality assumes remarkably little. $f$ need not be a sum, or linear, or monotone, or even continuous; it can be the chromatic number of a random graph or the length of a longest common subsequence — quantities with no closed form for the mean and no tractable variance. The mean may remain unknown, and the bound still says the value concentrates around it.

Applying the inequality therefore reduces to finding the constants $c_i$, and each $c_i$ answers a worst-case question: with the other inputs held at their least favourable values, how much can changing input $i$ alone change $f$?

Ways to work on it

• Walkthrough. Recover Hoeffding's inequality from McDiarmid's, and learn to find the bounded differences.
• Practice. Apply McDiarmid's inequality to combinatorial functions.
• Hardest. Find the bounded differences for a range of functions of independent variables.

Not sure where to start? Take the ten-question placement test.