Lune

STOC2026Top-tier venue

Mixing of General Biased Adjacent Transposition Chains

Reza Gheissari, Holden Lee, Eric Vigoda

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.

Questions to start from

Lune can draw on

the full paper ยท related work

Get the answer

Free to start. No credit card required.

Related papers

  1. Entropy decay in the Swendsen-Wang dynamics on โ„คdAntonio Blanca, Pietro Caputo, Daniel Parisi, Alistair Sinclair et al.STOC 2021 ยท 12 citations
  2. Trickle-Down in Localization Schemes and ApplicationsNima Anari, Frederic Koehler, Thuy-Duong VuongSTOC 2024 ยท 2 citations
  3. Low-temperature Ising dynamics with random initializationsReza Gheissari, Alistair SinclairSTOC 2022 ยท 13 citations
  4. Faster Mixing of the Jerrum-Sinclair ChainXiaoyu Chen, Weiming Feng, Zhe Ju, Tianshun Miao et al.FOCS 2025 ยท 11 citations
  5. Spatial mixing and the random-cluster dynamics on latticesReza Gheissari, Alistair SinclairSODA 2023 ยท 4 citations
Dusk over the sea between two cliffs drawn in fine vertical lines