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.
Reviewer: E.Kazarovitsky (Kiev)
MSC:
60J10 | Markov chains (discrete-time Markov processes on discrete state spaces) |
68Q25 | Analysis of algorithms and problem complexity |
05A05 | Permutations, words, matrices |