Hostname: page-component-78c5997874-8bhkd Total loading time: 0 Render date: 2024-11-09T01:30:45.563Z Has data issue: false hasContentIssue false

Convergence to stationary state for a Markov move-to-front scheme

Published online by Cambridge University Press:  14 July 2016

Eliane R. Rodrigues*
Affiliation:
Universidade de Brasilia
*
Postal address: Universidade de Brasília, Departamento de Matemática, Campus Universitário, Asa Norte, 70.919–900, Brasilia DF, Brazil.

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.

Type
Research Papers
Copyright
Copyright © Applied Probability Trust 1995 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

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

Aldous, D. (1989) Probability Approximations via the Poisson Clumping Heuristic. Applied Mathematical Sciences 77. Springer-Verlag, New York.Google Scholar
Aldous, D. and Diaconis, P. (1987) Strong stationary times and finite random walks. Adv. Appl. Math. 8, 6997.Google Scholar
Baum, L. E. and Billingsley, P. (1965) Asymptotic distributions for the coupon-collector's problem. Ann. Math. Statist. 36, 18351839.Google Scholar
Diaconis, P. (1988) Group Representations in Probability and Statistics. Lecture Notes — Monograph Series Vol. 11. Institute of Mathematical Statistics.Google Scholar
Diaconis, P., Fill, J. A. and Pitman, J. (1992) Analysis of top to random shuffles. Combinatorics, Probability and Computing 1, 135155.Google Scholar
Dobrow, R. P. (1994) The move-to-root self-organizing trees with Markov dependent requests. Preprint.Google Scholar
Dobrow, R. P. and Fill, J. A. (1994) The move-to-front rule for self-organizing lists with Markov dependent requests. Preprint.CrossRefGoogle Scholar
Doeblin, W. (1938) Exposé de la theorie des chaînes simples constantes de Markov à un nombre fini d'états. Rev. Math. de l'Union Interbalkanique 2, 77105.Google Scholar
Feller, W. (1968) An Introduction to Probability Theory and its Applications, Vol. I, 3rd edn. Wiley, New York.Google Scholar
Fill, J. A. (1993) An exact formula for the move-to-front rule for self-organizing lists. Preprint.Google Scholar
Goldstein, D. (1979) Maximal coupling, Z. Wahrscheinlichkeitsth. 46, 193204.Google Scholar
Griffeath, D. (1975) A maximal coupling for Markov chains. Z. Wahrscheinlichkeitsth. 31, 95106.Google Scholar
Griffeath, D. (1978) Coupling methods for Markov processes. Studies in Probability and Ergodic Theory. Advances in Mathematics Supplementary Studies 2, 143.Google Scholar
Hendricks, W. J. (1972) The stationary distribution of an interesting Markov chain. J. Appl. Prob. 9, 231233.Google Scholar
Lindvall, T. (1992) Lectures on the Coupling Method. Wiley, New York.Google Scholar
Rodrigues, E. R. (1993) A study of self-organising schemes and time to stationarity for some Markov processes. . Queen Mary and Westfield College, University of London.Google Scholar
Thorisson, H. (1986) On maximal and distributional coupling. Ann. Prob. 14, 873876.CrossRefGoogle Scholar