Mixing times of Markov chains for self‐organizing lists and biased permutations
Mixing times of Markov chains for self‐organizing lists and biased permutations
Abstract We study the mixing time of a Markov chain on biased permutations, a problem related to self‐organizing lists. We are given probabilities for all such that . The chain iteratively chooses two adjacent elements and , and swaps them with probability . It has been conjectured that is rapidly …