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. Stationary distributions can be computed from the Karnofsky--Rhodes and McCammond expansion of the right Cayley graph of the finite semigroup underlying the Markov chain. Using loop graphs, which are planar graphs consisting of a straight line with attached loops, there are rational expressions for the stationary distribution in the probabilities. From these we obtain bounds on the mixing time. In addition, we analyze the mixing time of the promotion Markov chain of Ayyer, Klee and the last author on linear extensions of a poset with $n$ vertices and provide a slight variant of this Markov chain with mixing time $O(n\log n)$. This is joint work with John Rhodes based on arXiv:2010.08879, arXiv:1902.01042 and arXiv:1711.10689.

Date and Venue

Start Date
Venue
Online Zoom meeting
End Date

Speaker

Anne Schilling

Speaker's Institution

Department of Mathematics, University of California, Davis

Files

Area

Semigroups, Automata and Languages

Financiamento