{"ID":2846304,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2511.02725","arxiv_id":"2511.02725","title":"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 $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} \\ge 1/2$ for all $i\u003cj$ and a simple monotonicity condition, the mixing time is polynomial. We prove that for any fixed $\\varepsilon\u003e0$, as long as $p_{ij} \u003e1/2+\\varepsilon$ for all $i\u003cj$, the mixing time is $Θ(n^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.","short_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-organiz...","url_abs":"https://arxiv.org/abs/2511.02725","url_pdf":"https://arxiv.org/pdf/2511.02725v1","authors":"[\"Reza Gheissari\",\"Holden Lee\",\"Eric Vigoda\"]","published":"2025-11-04T16:51:43Z","proceeding":"math.PR","tasks":"[\"math.PR\",\"cs.DS\"]","methods":"[\"Generative Adversarial Network\"]","has_code":false}