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

**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 T_{3} 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 x_{i}, then the transition matrix for T_{3} is

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 x_{1}, which is the probability of transitioning from 312 to 132 by moving book 1 to the front. Using that x_{1} + x_{2} +x_{3} = 1 (since they are probabilities), one can compute the eigenvalues 1, x_{1}, x_{2}, x_{3} and 0 with multiplicity 2. Hendricks computed the stationary distribution for the permutation π for general n.

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.*