×

On the transition probabilities of the move-to-front scheme. (English) Zbl 0805.60059

Consider \(n\) items \(B_ 1, B_ 2, \dots, B_ N\), and suppose that at each step one of them is chosen and removed to the left-hand end, while other items move to the right. If the choices are independent, then the successive configurations of the items form a Markov chain, known as the single shelf library chain. The author derives the \(n\)-step probabilities of the chain with a new method based on the close connection of the described scheme to the coupon-collector’s problem.

MSC:

60J10 Markov chains (discrete-time Markov processes on discrete state spaces)
68Q25 Analysis of algorithms and problem complexity
05A05 Permutations, words, matrices
Full Text: DOI