Past exam of the mathematics course of the University of Cambridge / 2010 / iii / Paper 12 / 2 / ii

Put $d=d_H(A,B)=\min \{d_H(\alpha ,\beta ):\alpha \in A,\beta \in B\}$, and define $f(\sigma )=d_H(\sigma ,A)$. The triangle inequality shows that $f$ is Lipschitz continuous with Lipschitz constant one. It vanishes on $A$, and $f\ge d$ on $B$. Let $\mu =\mathbb{E}f$ for a uniform permutation.

If $\mu \ge d/2$, apply the lower-tail bound proved in part (i):If $\mu <d/2$, apply its upper-tail bound:For $d=0$ the desired inequality is simply $\min \{|A|,|B|\}\le n!$. Hence in all casesThis uses only the precise one-sided concentration inequality from part (i) and the Hamming distance triangle inequality. The normalization of the distance matters: it counts mismatching coordinates, rather than dividing their number by $n$.