Date of Award
Doctor of Philosophy (PhD)
Svetlana Poznanović, Ph.D., Committee Chair
Michael Burr, Ph.D.
Shuhong Gao, Ph.D.
Matthew Macauley, Ph.D.
The Tsetlin library is a well-studied Markov model for how an arrangement of books on a library shelf evolves over time. It assumes that, given n books, one book is read and returned at the end of the shelf before another one is picked up. One of the most interesting properties of this Markov chain is that its spectrum can be computed exactly and its eigenvalues are linear in the transition probabilities. This result has been generalized in diﬀerent ways by various people. In this work, we investigate three generalizations given by the extended promotion Markov chain on linear extensions of a poset introduced by Ayyer, Klee, and Schilling (2014), the generalization given by Brown and Diaconis (1998) and Bidigare, Hanlon, and Rockmore (1999) to random-to-back pop shuﬄes, and the generalization by Bj¨orner (2008, 2009) to hierarchies of libraries. We consider combining these results to hierarchies of libraries where the states are linear extensions of associated posets. We also expand Ayyer, Klee, and Schilling’s result to a larger class of posets and derive convergence to stationarity.
Stasikelis, Kara, "Properties of Some Markov Chains on Linear Extensions of Posets" (2018). All Dissertations. 2104.