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 , {p_i, j}, for all i ≠ j, ij, such that p i, j = 1 − p j, i p_i, j=1-p_j, i . The chain ℳ n n 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 M_nn is rapidly mixing whenever the set of probabilities are "positively biased, " that is, p i, j ≥ 1 / 2 , {p_i, j1/2}, for all i < j i<j . We define two general classes and give the first proofs that ℳ n n 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.