$q$-deformations of the Tsetlin library

Abstract

The Tsetlin library is a random shuffling process on permutations of $n$ letters, where each letter $i$ can be interpreted as a book; book $i$ is brought to the front of the bookshelf with an assigned probability $x_i$. We define a $q$-deformation of the Tsetlin library by replacing the symmetric group action on permutations by the action of the type $A$ Iwahori-Hecke algebra. We compute the stationary distribution and spectrum of this Markov chain by relating it to a Markov chain on complete flags over the finite field vector space ${\mathbb{F}}_q^n$ and applying techniques from semigroup theory. We prove that for a natural choice of $x_i$ the total variation distance mixing time of the $q$-Tsetlin library on permutations of $n$ is $O(n)$ compared to $\Theta (n\log n)$ for the Tsetlin library at $q=1$, which demonstrates a phase transition. We also generalize the $q$-Tsetlin library to words (with repeated letters), and compute its stationary distribution and spectrum.

35 pages