Mixing Time for Some Adjacent Transposition Markov Chains

2016/04/04 by Shahrzad Haddadan, Peter Winkler, Haddadan, Shahrzad +1
Computer Science · Mathematics · #Algorithms and Data Compression #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Markov Chains and Monte Carlo Methods #Stochastic processes and statistical mechanics

paper · pdf · doi:10.48550/arxiv.1604.00870

openalex publication_date 2016/04/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We prove rapid mixing for certain Markov chains on the set S_n of permutations on 1,2,…,n in which adjacent transpositions are made with probabilities that depend on the items being transposed. Typically, when in state σ, a position i

Related

• Mixing of general biased adjacent transposition chains
• Elementary Bounds On Mixing Times for Decomposable Markov Chains
• Mixing Times of Self-Organizing Lists and Biased Permutations
• Rapid Mixing of k-Class Biased Permutations
• Partial mixing of semi-random transposition shuffles