Markov Chains for Promotion Operators
- Author(s): Ayyer, Arvind;
- Klee, Steven;
- Schilling, Anne
- et al.
Published Web Locationhttps://doi.org/10.1007/978-1-4939-0938-4_13
We consider generalizations of Schuetzenberger's promotion operator on the set L of linear extensions of a finite poset. This gives rise to a strongly connected graph on L. In earlier work (arXiv:1205.7074), we studied promotion-based Markov chains on these linear extensions which generalizes results on the Tsetlin library. We used the theory of R-trivial monoids in an essential way to obtain explicitly the eigenvalues of the transition matrix in general when the poset is a rooted forest. We first survey these results and then present explicit bounds on the mixing time and conjecture eigenvalue formulas for more general posets. We also present a generalization of promotion to arbitrary subsets of the symmetric group.