A combinatorial description of the spectrum for the Tsetlin library and its generalization to hyperplane arrangements (Q1974939)

The Tsetlin library (or move-to-front scheme) is a Markov chain providing a model for a self-regulating filing system. The states of the chain are the linear arrangements of \(n\) objects. Transitions change a given arrangement by moving some object to the first place. The transition probability for this move depends on the object moved. This chain has been studied by several authors [see \textit{J. A. Fill}, J. Theor. Probab. 9, No. 1, 113-160 (1996; Zbl 0837.60063)]. In this paper a sequence of generalizations of the Tsetlin library is introduced. For instance: Instead of moving just one object to the front a subset is moved retaining the relative order within the subset. This is the simplest case of a pop shuffle. Further generalizations culminate in a geometric model: a family of Markov chains within a setting of hyperplane arrangements. This family is general enough to include all chains studied in the paper. The central result is the determination of the eigenvalues of the transition matrix together with their multiplicities. This spectral result is used to give upper bounds on the convergence rates of the chain to its stationary distribution.