Date of Award
5-2018
Document Type
Dissertation
Degree Name
Doctor of Philosophy (PhD)
Department
Mathematical Sciences
Committee Member
Svetlana Poznanović, Ph.D., Committee Chair
Committee Member
Michael Burr, Ph.D.
Committee Member
Shuhong Gao, Ph.D.
Committee Member
Matthew Macauley, Ph.D.
Abstract
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 different 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 shuffles, 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.
Recommended Citation
Stasikelis, Kara, "Properties of Some Markov Chains on Linear Extensions of Posets" (2018). All Dissertations. 2104.
https://tigerprints.clemson.edu/all_dissertations/2104