Mixing of general biased adjacent transposition chains
Authors
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 $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 $i0$, as long as $p_{ij} >1/2+\varepsilon$ for all $i
