Mixing of general biased adjacent transposition chains
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866908628192067584 |
|---|---|
| author | Gheissari, Reza Lee, Holden Vigoda, Eric |
| author_facet | Gheissari, Reza Lee, Holden Vigoda, Eric |
| contents | 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<j$ and a simple monotonicity condition, the mixing time is polynomial. We prove that for any fixed $\varepsilon>0$, as long as $p_{ij} >1/2+\varepsilon$ for all $i<j$, 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_02725 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Mixing of general biased adjacent transposition chains Gheissari, Reza Lee, Holden Vigoda, Eric Probability Data Structures and Algorithms 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<j$ and a simple monotonicity condition, the mixing time is polynomial. We prove that for any fixed $\varepsilon>0$, as long as $p_{ij} >1/2+\varepsilon$ for all $i<j$, 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. |
| title | Mixing of general biased adjacent transposition chains |
| topic | Probability Data Structures and Algorithms |
| url | https://arxiv.org/abs/2511.02725 |