In this paper we consider the Markov chain formed by the operation of the move-to-front scheme. We show that the eigenvalues of the transition probability matrix are of the form pi, pi + pj, ···, where pi is the probability of selecting the ith item and N is the number of items; further, that the multiplicity of the eigenvalues of the form Σpi where the summation is over m items is equal to the number of permutations of N – m objects, ordered in some way, such that no object is in its natural position. Finally, we show that the Markov chain is lumpable – many times over.

We consider s ≦ n randomly chosen permutations of the numbers 1, 2, …, n, and write them under each other, thus forming an s × n matrix, called “random-batch”. A rule, prescribing how many elements of a column may occur exactly one time, how many may occur exactly two times, etc., is called a fixpoint-structure. Assuming each possible permutation to be chosen with equal probability, the number of columns having a certain fixpoint-structure F is a random variable X(F). The limiting distribution of X(F) for n→ ∞ is considered for different cases of s = s(n). The main result (Theorem 4) says, that the common distribution of a finite number t of given fixpoint-structures tends to the product of t Poisson-laws, n→ ∞.