Random transposition shuffle
ID: random-transposition-shuffle
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 .
New to topics? Read the docs here!