Investigation of a Markov Chain on Ferrers Boards
MetadataShow full item record
This thesis is an investigation of some of the basic combinatorial, algebraic and probabilistic properties of a Markov chain on Ferrers Boards (i.e., a Markov chain whose states are permutations on a given Ferrers Board). This is an extension of extensive work done over the last fifty years to understand the properties of a Markov chain known as the Tsetlin library. We will review the extensive literature surrounding the Tsetlin library, which also allows for the problem to be contextualized as a particularly nice model of a procedure for searching a database of files. Some of the specific questions we will explore include the transitivity of the Tsetlin library (in fact, we will prove that the extended library is transitive and at most n steps are needed to reach any state from an arbitrarily chosen state); the Tsetlin library’s relation to permutation inversions and some other combinatorial statistics; and finally the computation of the Tsetlin library’s stationary distribution and eigenvalues in some easy cases. Although our analysis of the combinatorial aspects of the extended Tsetlin library is complete, we have been unable to fully describe the probabilistic aspects of the Tsetlin library. We are able to describe the stationary distribution for specific easy cases, but further analysis for more complicated cases has proven difficult. Computations have been done using the mathematical software Maple to determine if any patterns may be discerned from specific examples of the more complicated cases. However, the data indicates that the actual stationary distribution differs from our conjectured formula for the stationary distribution, which gives a need for further analysis in future work. We have also not been able to describe the eigenvalues or convergence to stationary for even the simplest Ferrers boards, but we do have various computations which we hope will be the basis for future exploration of these topics.
Linz, William Barham (2016). Investigation of a Markov Chain on Ferrers Boards. Master's thesis, Texas A & M University. Available electronically from