pith. sign in

arxiv: 1412.7488 · v4 · pith:VN44TII6new · submitted 2014-12-23 · 🧮 math.PR · math.CO

Spectral gap for random-to-random shuffling on linear extensions

classification 🧮 math.PR math.CO
keywords random-to-randomshufflingextensionslinearposettimeabovebounded
0
0 comments X
read the original abstract

In this paper, 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 \log n)$. We conjecture that the mixing time is in fact $O(n \log n)$ as for the usual random-to-random shuffling.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.