Mixing of general biased adjacent transposition chains

2025/11/04 by Gheissari, Reza, Lee, Holden, Vigoda, Eric
Mathematics · #Stochastic processes and statistical mechanics #Markov Chains and Monte Carlo Methods #Advanced Combinatorial Mathematics

paper · doi:10.48550/arxiv.2511.02725

Abstract

We analyze the general biased adjacent transposition shuffle process, which is a well-studied Markov chain on the symmetric group S_n. In each step, an adjacent pair of elements i and j are chosen, and then i is placed ahead of j with probability p_ij. This Markov chain arises in the study of self-organizing lists in theoretical computer science, and has close connections to exclusion processes from statistical physics and probability theory. Fill (2003) conjectured that for general p_ij satisfying p_ij ≥ 1/2 for all i0, as long as p_ij >1/2+ε for all i

Citations

• An interesting spectral gap problem, from Jim Fill
• Iterated Decomposition of Biased Permutations Via New Bounds on the\n Spectral Gap of Markov Chains
• Rapid Mixing of k-Class Biased Permutations
• Kardar-Parisi-Zhang Universality
• Mixing times of the biased card shuffling and the asymmetric exclusion process

Related

• Mixing Times of Self-Organizing Lists and Biased Permutations
• Rapid Mixing of k-Class Biased Permutations
• Random Walks on the Symmetric Group: Cutoff for One-sided Transposition\n Shuffles
• Mixing Time for Some Adjacent Transposition Markov Chains
• Cutoff for a One-sided Transposition Shuffle