Séminaire Lotharingien de Combinatoire, 85B.27 (2021), 12 pp.
John Rhodes and Anne Schilling
Mixing Time for Markov Chain on Linear Extensions
Abstract.
We provide a general framework for computing mixing times of finite Markov chains when its minimal ideal is left zero.
Our analysis is based on combining results by Brown and Diaconis with our previous work on stationary distributions of
finite Markov chains. We introduce a new Markov chain on linear extensions of a poset with n vertices, which is a variant
of the promotion Markov chain of Ayyer, Klee and the last author, and show that it has a mixing time O(n log n).
Received: December 1, 2020.
Accepted: March 1, 2021.
Final version: April 29, 2021.
The following versions are available: