ON THE MOVE-TO-FRONT SCHEME WITH MARKOV DEPENDENT REQUESTS

In this paper we consider the operation of the move-to-front scheme wh ere the requests form a Markov chain of N states with transition proba bility matrix P. It is shown that the configurations of items at succe ssive requests form a Markov chain. and its transition probability mat rix has eigenvalues that are the eigenvalues of all the principal subm atrices of P except those of order N-1. We also show that the multipli city of the eigenvalues of submatrices of order m is the number of der angements of N-m objects. The last result is shown to be true even if P is not a stochastic matrix.