LIMITS AND RATES OF CONVERGENCE FOR THE DISTRIBUTION OF SEARCH COST UNDER THE MOVE-TO-FRONT RULE

We derive upper and lower bounds on total variation distance to statio narity for the distribution of search cost under the move-to-front (MT F) rule for self-organizing lists with i.i.d. record requests. These e nable us to obtain sharp rates of convergence for several standard exa mples of weights, including Zipf's law and geometric weights, as the l ength of the list becomes large. The upper bound also shows that a num ber of moves of the order of the length of the list is uniformly suffi cient for near-stationarity over all choices of weights. Concerning th e stationary search cost distribution itself, we use a representation obtained by considering the continuized MTF Markov chain to derive, fo r each of the standard examples, the asymptotic distribution for long lists.