Talagrand's concentration inequality

Remarks

The theorem holds, with the same proof, for products of general probability spaces, provided the sets involved are measurable. Talagrand proved the stronger bound $\int_\Omega e^{d_T(x, A)^2 / 4} \, P(dx) \le 1 / P(A)$, by induction on $n$; Markov's inequality applied to $e^{d_T^2/4}$ gives the statement. The convex distance is at least the normalised Hamming distance $\min_{y \in A} \#\set{i : x_i \ne y_i} / \sqrt{n}$, by the choice $\alpha_i = 1/\sqrt{n}$, so the theorem implies Hamming concentration. A main consequence concerns convex Lipschitz functions. Let $X_1, \dots, X_n$ be independent with values in $[0, 1]$, and let $F \colon [0, 1]^n \to \R$ be convex and $1$-Lipschitz for the Euclidean norm. Then $P(\abs{F(X) - m} \ge t) \le C e^{-c t^2}$ for absolute constants $C, c > 0$, where $m$ is a median of $F(X)$. The bound does not depend on $n$, while bounded-difference methods would give a bound that gets worse with the dimension for this class. It is used, for example, to show that the length of the longest increasing subsequence of a random permutation is concentrated around its median.

Going deeper

For a student

Talagrand's inequality is a central result of the concentration of measure phenomenon in product spaces. It goes beyond McDiarmid's inequality because the distance adapts to each point through the weights $\alpha$, which yields dimension-free bounds for convex Lipschitz functions and for functions with small certificates. Applications include the largest eigenvalue of random matrices with bounded entries, longest increasing subsequences, and combinatorial optimisation problems on random inputs.