Hostname: page-component-7b7567c8c-7pwfn Total loading time: 0 Render date: 2026-11-14T08:02:16.501Z Has data issue: false hasContentIssue false
  • English
  • Français

On the move-to-front scheme with Markov dependent requests

Part of:Theory of dataMarkov processes

Published online by Cambridge University Press:  14 July 2016

R. M. Phatarfod,
A. J. Pryde and
David Dyte
R. M. Phatarfod*
Affiliation:
Monash University
A. J. Pryde*
Affiliation:
Monash University
David Dyte*
Affiliation:
Monash University
*
∗ Postal address: Department of Mathematics, Monash University, Clayton, Victoria 3168, Australia.
∗ Postal address: Department of Mathematics, Monash University, Clayton, Victoria 3168, Australia.
∗ Postal address: Department of Mathematics, Monash University, Clayton, Victoria 3168, Australia.
Get accessRights & Permissions [Opens in a new window]

Abstract

In this paper we consider the operation of the move-to-front scheme where the requests form a Markov chain of N states with transition probability matrix P . It is shown that the configurations of items at successive requests form a Markov chain, and its transition probability matrix has eigenvalues that are the eigenvalues of all the principal submatrices of P except those of order N—1. We also show that the multiplicity of the eigenvalues of submatrices of order m is the number of derangements of N — m objects. The last result is shown to be true even if P is not a stochastic matrix.

Keywords

MOVE-TO-FRONTMARKOV CHAINTRANSITION MATRIXEIGENVALUES

MSC classification

Primary:60J10: Markov chains (discrete-time Markov processes on discrete state spaces)
Secondary:68P10: Searching and sorting68P05: Data structures

Information

Type
Short Communications
Information
Journal of Applied Probability , Volume 34 , Issue 3 , September 1997, pp. 790 - 794
Copyright
Copyright © Applied Probability Trust 1997 

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.)

Article purchase

Temporarily unavailable

References

Aven, O. I., Coffman, E. G. and Kogan, Y. A. (1987) Stochastic Analysis of Computer Storage. Reidel, Dordrecht.Google Scholar
Bentley, J. O. and Mcgeoch, C. C. (1985) Amortized analyses of self-organizing sequential search heuristics. Commun. ACM 28, 404–411.Google Scholar
Bitner, J. R. (1979) Heuristics that dynamically organize data structures. SIAM J. Comput. 8, 82–110.Google Scholar
Dobrow, R. P. and Fill, J. A. (1995) The move-to-front rule for self-organizing lists with Markov dependent requests. In Discrete Probability and Algorithms (IMA Volumes in Mathematics and its Applications 72) . ed. Aldous, D. et al. Springer, Berlin.Google Scholar
Hendricks, W. J. (1972) The stationary distribution of an interesting Markov chain. J. Appl. Prob. 9, 231–233.Google Scholar
Hendricks, W. J. (1976) An account of self-organizing systems. SIAM J. Comput. 5, 715–723.Google Scholar
Knuth, D. E. (1973) The Art of Computer Programming (T.3: Sorting and Searching) . Addison-Wesley, New York.Google Scholar
Lam, K., Leung, M. and Siu, M. (1984) Self-organizing files with dependent access. J. Appl. Prob. 21, 343–359.Google Scholar
Phatarfod, R. M. (1991) On the matrix occurring in a linear search problem. J. Appl. Prob. 28, 336–346.Google Scholar
Phatarfod, R. M. and Dyte, D. (1993) On the move-to-front scheme with Markov dependent requests. Statistics Research Report No. 232. Monash University.Google Scholar