Mixing times of Markov chains for self‐organizing lists and biased permutations. Issue 4 (20th April 2022) - Bhakta, Prateek; Miracle, Sarah; Randall, Dana; Streib, Amanda Pascoe
Abstract: We study the mixing time of a Markov chain on biased permutations, a problem related to self‐organizing lists. We are given probabilities { p i, j }, $$ \left\{{p}_{i, j}\right\}, $$ for all i ≠ j, $$ i\ne j, $$ such that p i, j = 1 − p j, i $$ {p}_{i, j}=1-{p}_{j, i} $$ . The chain ℳ n n $$ {\mathcal{M}}_{nn} $$ iteratively chooses two adjacent elements i $$ i $$ and j $$ j $$, and swaps them with probability p i, j $$ {p}_{i, j} $$ . It has been conjectured that ℳ n n $$ {\mathcal{M}}_{nn} $$ is rapidly mixing whenever the set of probabilities are "positively biased, " that is, { p i, j ≥ 1 / 2 }, $$ \left\{{p}_{i, j}\ge 1/2\right\}, $$ for all i < j $$ i<j $$ . We define two general classes and give the first proofs that ℳ n n $$ {\mathcal{M}}_{nn} $$ is rapidly mixing for both. We also demonstrate that the chain can have exponential mixing time, disproving the most general version of this conjecture.