= Solution
Use the uniform <probability measure> on the <symmetric group> $S_n$ and the unnormalized <Hamming distance>
$$
d_H(\sigma,\tau)=|\{j:\sigma(j)\ne\tau(j)\}|.
$$
Let $f:S_n\to\mathbb R$ have <Lipschitz constant> $K>0$ for this distance. We will prove the one-sided <concentration inequalities>
$$
\boxed{\mathbb P(f-\mathbb Ef\geq t),\ \mathbb P(f-\mathbb Ef\leq-t)
\leq\exp\!\left(-\frac{t^2}{2nK^2}\right),\qquad t\geq0.}
$$
Consequently $\mathbb P(|f-\mathbb Ef|\geq t)\leq2e^{-t^2/(2nK^2)}$ for $t>0$. A zero <Lipschitz constant> makes $f$ constant, so that case is immediate.
Let $\sigma$ be a uniform <permutation>, reveal $\sigma(1),\ldots,\sigma(k)$ successively, and define the <Doob exposure martingale>
$$
M_k=\mathbb E[f(\sigma)\mid\sigma(1),\ldots,\sigma(k)],\qquad
M_0=\mathbb Ef,\quad M_n=f(\sigma).
$$
Fix the first $k-1$ images. For an available value $a$, let $h(a)$ be the conditional mean when $\sigma(k)=a$. Given two available values $a,b$, left-composition with the <transposition> exchanging $a,b$ is a <bijection> from completions with next image $a$ to completions with next image $b$. It fixes the previously exposed images and changes exactly two coordinates of each complete <permutation>. Since conditional completions are uniform, averaging the <Lipschitz condition> over this pairing gives $|h(a)-h(b)|\leq2K$.
Thus, conditionally on the first $k-1$ images, $M_k-M_{k-1}$ has mean zero and takes values in an interval of length at most $2K$. We need the range-length version of the <Hoeffding lemma>: if a real <random variable> $Z$ has mean zero and lies in an interval of length $\ell$, then
$$
\mathbb E e^{\lambda Z}\leq e^{\lambda^2\ell^2/8}\qquad(\lambda\in\mathbb R).
$$
Here is a proof. For $\psi(\lambda)=\log\mathbb E e^{\lambda Z}$, differentiation gives $\psi''(\lambda)=\operatorname{Var}_\lambda(Z)$ under the exponentially tilted <probability distribution>. Any distribution on an interval of length $\ell$ has <variance> at most $\ell^2/4$, because its squared distance from the interval midpoint is at most $\ell^2/4$. Since $\psi(0)=\psi'(0)=0$, integrating this second-derivative bound gives the lemma for both signs of $\lambda$. The same argument holds for every conditional distribution.
Apply it conditionally to each <martingale difference> and use the tower property of <conditional expectation> repeatedly:
$$
\mathbb E e^{\lambda(M_n-M_0)}\leq e^{n\lambda^2K^2/2}.
$$
The <exponential Markov bound> now gives, for $\lambda>0$,
$$
\mathbb P(M_n-M_0\geq t)\leq\exp(-\lambda t+n\lambda^2K^2/2).
$$
Choose $\lambda=t/(nK^2)$ to obtain the upper tail in the box, and apply the argument to $-f$ for the lower tail. This proves <concentration of Lipschitz functions on the symmetric group>. Using only the bound $|M_k-M_{k-1}|\leq2K$ in the absolute-increment <Azuma-Hoeffding inequality> would lose a factor four in the exponent; the conditional range length is what yields the constant needed in part (ii).
Back to article page
