Spectral Gap for Random-to-Random Shuffling on Linear Extensions
Ayyer, Arvind, Schilling, Anne, Thiery, Nicolas M · NOT FOUND REPOSITORY (Indian Institute of Science Bangalore) · 2017
In this article, we propose a new Markov chain which generalizes random-to-random shuffling on permutations to random-to-random shuffling on linear extensions of a finite poset of size n. We conjecture that the second largest eigenvalue of the transition matrix is bounded above by (1 + 1/n)(1 - 2/n) with equality when the poset is disconnected. This Markov chain provides a way to sample the linear extensions of the poset with a relaxation time bounded above by n(2)/(n + 2) and a mixing time of O(n(2)logn). We conjecture that the mixing time is in fact O(nlogn) as for the usual random-to-random shuffling.