Choose two positions independently and uniformly from and swap them. This Markov chain on the symmetric group holds with Probability and assigns Probability to each unordered transposition. Its stationary distribution is uniform, and its ordinary spectral gap is for . The latter follows from the Aldous spectral gap theorem: the single-label continuous-time Markov chain has rate between every pair of positions, whose mean-zero eigenvalues are all .
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.
Articles by others on the same topic
There are currently no matching articles.