Mixing Times of Self-Organizing Lists and Biased Permutations

Prateek Bhakta, Sarah Miracle, Dana Randall +1

Sampling permutations from S_n is a fundamental problem from probability theory. The nearest neighbor transposition chain \cal{M}}_{nn} is known to converge in time Θ(n^3 \log n) i…