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.

Share

COinS