Limiting search cost distribution for the move-to-front rule with random request probabilities

摘要

Consider a list of n files whose popularities are random. The list is updated according to the move-to-front rule. When the induced Markov chain is at equilibrium, we explicitly compute the limiting distribution of the search-cost per item as it tends to infinity. The uniform distribution results in the largest search cost. (c) 2005 Elsevier B.V. All rights reserved.