2012/04/15 by Prateek Bhakta, Sarah Miracle, Bhakta, Prateek +5
Computer Science · Mathematics · #Algorithms and Data Compression #Bayesian Methods and Mixture Models #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Stochastic processes and statistical mechanics #cs.DM
paper · pdf · doi:10.48550/arxiv.1204.3239
21 pages
arxiv created 2012/04/15 · openalex publication_date 2012/04/15 · arxiv updated 2012/04/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Sampling permutations from Sn is a fundamental problem from probability theory. The nearest neighbor transposition chain \calMnn is known to converge in time Θ(n3 log n) in the uniform case and time Θ(n2) in the constant bias case, in which we put adjacent elements in order with probability p ≠ 1/2 and out of order with probability 1-p. Here we consider the variable bias case where we put adjacent elements x<y in order with probability px,y and out of order with probability 1-px,y. The problem of bounding the mixing rate of Mnn was posed by Fill and was motivated by the Move-Ahead-One self-organizing list update algorithm. It was conjectured that the chain would always be rapidly mixing if 1/2 ≤ px,y ≤ 1 for all x < y, but this was only known in the case of constant bias or when px,y is equal to 1/2 or 1, a case that corresponds to sampling linear extensions of a partial order. We prove the chain is rapidly mixing for two classes: "Choose Your Weapon," where we are given r1,..., rn-1 with ri ≥ 1/2 and px,y=rx for all x<y (so the dominant player chooses the game, thus fixing his or her probability of winning), and "League Hierarchies," where there are two leagues and players from the A-league have a fixed probability of beating players from the B-league, players within each league are similarly divided into sub-leagues with a possibly different fixed probability, and so forth recursively. Both of these classes include permutations with constant bias as a special case. Moreover, we also prove that the most general conjecture is false by constructing a counterexample where 1/2 ≤ px,y ≤ 1 for all x< y, but for which the nearest neighbor transposition chain requires exponential time to converge.