Article contents
Convergence to stationary state for a Markov move-to-front scheme
Published online by Cambridge University Press: 14 July 2016
Abstract
This work considers items (e.g. books, files) arranged in an array (e.g. shelf, tape) with N positions and assumes that items are requested according to a Markov chain (possibly, of higher order). After use, the requested item is returned to the leftmost position of the array. Successive applications of the procedure above give rise to a Markov chain on permutations. For equally likely items, the number of requests that makes this Markov chain close to its stationary state is estimated. To achieve that, a coupling argument and the total variation distance are used. Finally, for non-equally likely items and so-called p-correlated requests, the coupling time is presented as a function of the coupling time when requests are independent.
Keywords
- Type
- Research Papers
- Information
- Copyright
- Copyright © Applied Probability Trust 1995
Footnotes
Most of this work was done while the author was doing her Ph.D. at Queen Mary and Westfield College, University of London, UK.
References
- 3
- Cited by