UC Davis Mathematics

Select a news year:2019 2017 2016 2015 2013 2012 2009 2008

February 2019

by Anne Schilling

Suppose your library has one shelf with n books. If someone checks out book i and returns it, this book gets placed at the beginning of the shelf. After a while, the popular books accumulate at the front of the bookshelf.

This library is called the Tsetlin library. It is a Markov chain Tn, where the states are the n! permutations of the n books. The Tsetlin library T3 is depicted in the figure at the left, where an arrow labeled 1 ≤ i ≤ n from permutation π to permutation π’ means that book i is moved to the front. The question is now, what will be the distribution of books if we wait for a while? In mathematics, this is called the stationary distribution, which is the right eigenvector with eigenvalue 1 of the transition matrix of the Markov chain. If book i is picked with probability xi, then the transition matrix for T3 is

$$ M_{T_3}= \begin{pmatrix} x_1 & 0 &x_1&x_1&0&0\\ 0 & x_1 &0 &0 &x_1&x_1\\ x_2 & x_2 &x_2&0 &0&0\\ 0 & 0 &0 &x_2&x_2&x_2\\ x_3 & x_3 &0 &0 &x_3&0\\ 0 & 0 &x_3&x_3&0&x_3 \end{pmatrix}, $$

where we have ordered the 6 permutations as (123; 132; 213; 231; 312; 321). For example, the entry in the column associated to permutation 312 and the row associated to permutation 132 (which is the entry in row 2 and column 5) is x1, which is the probability of transitioning from 312 to 132 by moving book 1 to the front. Using that x1 + x2 +x3 = 1 (since they are probabilities), one can compute the eigenvalues 1, x1, x2, x3 and 0 with multiplicity 2. Hendricks computed the stationary distribution for the permutation π for general n.

$$ \psi_{\pi} = \prod_{i=1}^n \frac{x_{\pi_i}}{1-\sum_{j=1}^{i-1} x_{\pi_j}}. $$

Can we compute the stationary distribution of a general nite Markov chain? The answer is Yes, using new techniques from semigroup theory. In fact, this means that one can compute an eigenvector of a matrix without any linear algebra!

Book photo modified from one provided by freestockcenter, on freepik.com.