Mixing Times of Self-Organizing Lists and Biased Permutations
Prateek Bhakta, Sarah Miracle, Dana Randall, Amanda Pascoe Streib · arXiv (Cornell University) · 2012
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) in the uniform case and time Θ(n^2) in the constant bias case, in which we put adjacent elements in order with probability p eq 1/2 and out of order with probability 1-p. Here we consider the variable bias case where we put adjacent elements x