We consider the move-to-front self-organizing linear search heuristic where the sequence of record requests is a Markov chain. Formulas are derived for the transition probabilities and stationary distribution of the permutation chain. The spectral structure of the chain is presented explicitly. Bounds on the discrepancy from stationarity for the permutation chain are computed in terms of the corresponding discrepancy for the request chain, both for separation and for total variation distance.

Back to Discrete Probability and Algorithms Table of Contents

Back to the IMA Home Page