Skip to main content
![Creative Commons 'BY-NC-ND' version 4.0 license]()
Mixing time for Markov chain on linear extensions
Published Web Location
https://www.mat.univie.ac.at/~slc/wpapers/FPSAC2021/27Rhodes.pdfNo data is associated with this publication.
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).
Many UC-authored scholarly publications are freely available on this site because of the UC's open access policies. Let us know how this access is important for you.