the transportation-cost (Marton) inequality
/ MAR-tohn /
The transportation-cost approach, pioneered by Katalin Marton, derives concentration of measure from a completely different and very robust principle: an inequality that bounds the Wasserstein cost of transporting any other probability measure onto your reference measure by the square root of the relative entropy (Kullback-Leibler divergence) of that measure with respect to the reference. Its great virtue is that it extends concentration cleanly to DEPENDENT random variables — Markov chains, mixing processes — where the martingale and entropy methods need extra hypotheses.
A measure mu on a metric space satisfies a transportation-cost inequality of order p (a 'T_p inequality') with constant C if, for every other measure nu absolutely continuous with respect to mu, W_p(nu, mu) <= sqrt(2 C * KL(nu || mu)), where W_p is the p-Wasserstein distance and KL is relative entropy. The case p = 1 (Marton's T_1, equivalent to sub-Gaussian concentration of Lipschitz functions by a duality argument) and p = 2 (Talagrand's T_2, which is implied by a log-Sobolev inequality and is even stronger) are the central ones. The mechanism by which such an inequality gives concentration is elegant: take A a set of measure at least 1/2, let nu be mu conditioned on A; then KL(nu || mu) <= log(1/mu(A)) = log 2, so W_1(nu, mu) is small, meaning the conditioned measure is close to mu in transport distance, which forces most of mu's mass to sit within distance O(1) of A — exactly concentration of measure. Marton's masterstroke was a coupling argument (Marton coupling) that proves the T_1 inequality for product measures, and more importantly for measures satisfying a contraction condition on their conditional distributions, which covers contracting Markov chains.
Why this route matters: it is the most natural framework for concentration of functions of DEPENDENT variables. For a Markov chain whose one-step transition is a contraction in Wasserstein distance (Dobrushin-type condition), Marton's method yields McDiarmid-style concentration for Lipschitz functionals of the whole trajectory, with the constant degraded only by the mixing/contraction coefficient. The honest caveats: the constant C in the transportation inequality is exactly the concentration constant, so the method is only as good as the transport constant you can prove, and for slowly-mixing chains C blows up. Also, T_2 (sufficient for dimension-free Gaussian-style concentration of the L^2-Lipschitz functions, and the form that comes from log-Sobolev) is strictly stronger than T_1; conflating the two over-claims the available concentration.
For a product measure on [0,1]^n, Marton's T_1 inequality holds with constant n/4 in the Hamming-weighted W_1, and dualizing recovers McDiarmid: any 1-Lipschitz (in weighted Hamming) function f satisfies P(f - E[f] >= t) <= exp(-2 t^2 / n). The strength of the method is that the SAME derivation, with the constant replaced by n/(4(1-gamma)^2), works for a Markov chain with contraction coefficient gamma < 1.
Transportation inequalities extend concentration to dependent (mixing) variables.
The concentration constant is exactly the transport constant C, so slowly-mixing chains give weak concentration. T_2 is strictly stronger than T_1 and is what log-Sobolev delivers; do not claim T_2-level (dimension-free L^2) concentration from a T_1 inequality.