Mixing times of Markov chains for self‐organizing lists and biased permutations. Issue 4 (20th April 2022)

• Record Type: Journal Article
• Authors: Bhakta, Prateek; Miracle, Sarah; Randall, Dana; Streib, Amanda Pascoe
• Is Part Of: Random structures & algorithms. Volume 61:Issue 4(2022)
• Page Start: 638
• Page End: 665
• Publication Date: 2022-04-20
• Subjects: ASEP -- biased permutations -- inversion tables -- Markov chains -- self‐organizing lists; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.21082
• Languages: English
• ISSNs: 1042-9832

Abstract

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.