Seminar | November 9 | 3:10-4 p.m. | 340 Evans Hall
Anne Schilling, UC Davis
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.
lfzhang@berkeley.edu, 510-0000000
Alan Hammond, alanmhammond@yahoo.co.uk, 510-000-0000