Mixing of General Biased Adjacent Transposition Chains
Abstract
We analyze the general biased adjacent transposition shuffle process, which is a well-studied Markov chain on the symmetric group ๐ ๐ . In each step, an adjacent pair of elements ๐ and ๐ are chosen, and then ๐ is placed ahead of ๐ with probability ๐ ๐๐ . 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 ๐ ๐๐ satisfying ๐ ๐๐ โฅ 1/2 for all ๐ < ๐ and a simple monotonicity condition, the mixing time is polynomial. We prove that for any fixed ๐ > 0, as long as ๐ ๐๐ > 1/2 + ๐ for all ๐ < ๐, the mixing time is ฮ(๐ 2 ) and exhibits pre-cutoff. Our key technical result is a form of spatial mixing for the general biased transposition chain after a suitable burn-in period. In order to use this for a mixing time bound, we adapt multiscale arguments for mixing times from the setting of spin systems to the symmetric group.
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
Related papers
- Entropy decay in the Swendsen-Wang dynamics on โคdAntonio Blanca, Pietro Caputo, Daniel Parisi, Alistair Sinclair et al.STOC 2021 ยท 12 citations
- Trickle-Down in Localization Schemes and ApplicationsNima Anari, Frederic Koehler, Thuy-Duong VuongSTOC 2024 ยท 2 citations
- Low-temperature Ising dynamics with random initializationsReza Gheissari, Alistair SinclairSTOC 2022 ยท 13 citations
- Faster Mixing of the Jerrum-Sinclair ChainXiaoyu Chen, Weiming Feng, Zhe Ju, Tianshun Miao et al.FOCS 2025 ยท 11 citations
- Spatial mixing and the random-cluster dynamics on latticesReza Gheissari, Alistair SinclairSODA 2023 ยท 4 citations
