= Concentration of Lipschitz functions on the symmetric group
{title2=$\mathbb P(|f-\mathbb Ef|\geq t)\leq2\exp(-t^2/(2nK^2))$}
Equip the <symmetric group> $S_n$ with its uniform <probability measure> and unnormalized <Hamming distance>. If $f$ has <Lipschitz constant> $K$, it obeys the displayed two-sided bound, and each one-sided tail has the same exponential without the factor two. Reveal a uniform <permutation> one image at a time. Two possible next images have completion sets paired by swapping those two values, changing exactly two coordinates. Thus the corresponding conditional means differ by at most $2K$. Each increment of the <Doob exposure martingale> has conditional range length at most $2K$. Applying the conditional <Hoeffding lemma> gives $\mathbb E e^{\lambda(f-\mathbb Ef)}\leq e^{n\lambda^2K^2/2}$; optimizing the <exponential Markov bound> proves the bound. A mere absolute-increment bound of $2K$ gives a weaker constant, so using the range length matters.
Back to article page
