Back to search

Clemson University

Properties of Some Markov Chains on Linear Extensions of Posets

Abstract

dc:description.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.

Degree

thesis:*
Name thesis:degree_name
Doctor of Philosophy (PhD)
Level thesis:degree_level
Dissertation
Discipline thesis:degree_discipline
Mathematical Sciences

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Stasikelis, Kara
Contributors dc:contributor
  • Svetlana Poznanović, Ph.D., Committee Chair
  • Michael Burr, Ph.D.
  • Shuhong Gao, Ph.D.
  • Matthew Macauley, Ph.D.

Identifiers

dc:identifier.*
Repository record dc:identifier
https://open.clemson.edu/all_dissertations/2104

Chain of custody

source
Harvested from
Clemson University
Base URL
open.clemson.edu/do/oai/
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Stasikelis, Kara. Properties of Some Markov Chains on Linear Extensions of Posets. Dissertation thesis, https://open.clemson.edu/all_dissertations/2104