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

Abstract

Consider a list of $n$ files whose popularities are random. These files are updated according to the move-to-front rule and we consider the induced Markov chain at equilibrium. We give the exact limiting distribution of the search-cost per item as $n$ tends to infinity. Some examples are supplied.

move-to-front, search cost, random discrete distribution, limiting distribution, size biased permutation