On the move-to-front scheme with Markov dependent requests

On the move-to-front scheme with Markov dependent requests

0.00 Avg rating0 Votes
Article ID: iaor1999343
Country: United Kingdom
Volume: 34
Issue: 3
Start Page Number: 790
End Page Number: 794
Publication Date: Sep 1997
Journal: Journal of Applied Probability
Authors: , ,
Keywords: sorting
Abstract:

In this paper we consider the operation of the move-to-front scheme where the requests form a Markov chain of N states with transition probability matrix P. It is shown that the configurations of items at successive requests form a Markov chain, and its transition probability matrix has eigenvalues that are the eigenvalues of all the principal submatrices of P except those of order N – 1. We also show that the multiplicity of the eigenvalues of submatrices of order m is the number of derangements of Nm objects. The last result is shown to be true even if P is not a stochastic matrix.

Reviews

Required fields are marked *. Your email address will not be published.