Past exam of the mathematics course of the University of Cambridge 2017 iii Paper 215 4 c Solution Created 2026-10-03 Updated 2026-10-06
The reference kernel printed in the hint has total mass , so it is not a Markov kernel. We explicitly replace it by the normalized random transposition shuffle: choose two positions independently and uniformly and swap them. Its probabilities areThese sum to one, and its ordinary spectral gap is , the value intended in the hint. This value can also be certified by the Aldous spectral gap theorem: the single-label generator has rate between distinct positions, so on centered functions it acts as multiplication by . Both shuffles have the same uniform distribution on a finite set as stationary distribution.
We use the Canonical paths comparison theorem in the following precise form. For two finite reversible Markov chains with the same positive stationary distribution , route each directed transition of along a positive-capacity path of . Ifthen and . Indeed, telescope each difference along its path, apply the Cauchy-Schwarz inequality, and sum with weights . The load definition gives the Dirichlet form of a Markov chain inequality; the common variance denominator then gives the spectral gap inequality. Identity transitions use empty paths.
Put . A transposition is routed using the wordof length . Each generator occurs at most twice; write its occurrence count as . For a fixed directed adjacent edge and each occurrence of in a word, there is exactly one starting permutation whose translated word crosses this edge at that occurrence. This follows because right multiplication by the prefix is a bijection of the symmetric group. Hence the uniform stationary factors cancel in the comparison load, leavingThe crude bounds , , and imply . ThereforeOnly pairs with contribute, and there are of these. Keeping this restriction gives the stronger and . Neither comparison bound needs the exact adjacent-shuffle spectral gap; the normalization repair of the reference kernel is essential.
Separation chain for two labels in a circular transposition shuffle Created 2026-10-14 Updated 2026-11-05
Place six positions on a cycle and distinguish two labels. At each step choose one of the fifteen unordered pairs of distinct positions uniformly and transpose their contents. This convention excludes identity moves. The shorter circular distance between the distinguished labels takes values . Cycle symmetry and exchangeability of the other labels make this distance a Lumped Markov chain.
Counting transpositions gives the transition matrix and Stationary distributionThe stationary weights also follow by counting unordered position pairs: six pairs have distance one, six have distance two, and three are opposite. If has every row equal to , then and . Starting with adjacent labels, the Probability of opposite labels after steps is therefore .
The parent Random transposition shuffle uses a different convention: two positions are sampled independently, allowing an identity move with Probability . Under that convention the distance transition matrix is , and the opposite-label Probability is . Explicitly stating the sampling convention prevents a spurious change in the convergence rate.