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: