The performance of the move-to-front scheme under some particular forms of Markov requests

The move-to-front scheme is studied taking into account some forms of Markov dependence for the way items are requested. One of the dependences specifically rules out two consecutive requests for the same item. The other is the so-called p-correlation. An expression for the stationary distribution o...

Full description

Saved in:
Bibliographic Details
Published in:Journal of applied probability 1995-12, Vol.32 (4), p.1089-1102
Main Author: Rodrigues, Eliane R.
Format: Article
Language:English
Subjects:
Applied sciences
Computer science
control theory
systems
Computer systems performance. Reliability
Distribution
Equations
Exact sciences and technology
Markov analysis
Markov chains
Markov processes
Mathematics
Preprints
Probability
Probability and statistics
Probability theory and stochastic processes
Random variables
Research Papers
Sciences and techniques of general use
Search time
Software
Studies
Taboos
Time dependence
Transition probabilities
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The move-to-front scheme is studied taking into account some forms of Markov dependence for the way items are requested. One of the dependences specifically rules out two consecutive requests for the same item. The other is the so-called p-correlation. An expression for the stationary distribution of the sequence of arrangements of items is given in each case. A necessary and sufficient condition for these distributions to belong to a particular class of distributions is also given. The mean search time for an item is calculated for each form of dependence and these are compared with the value obtained in the case of independent requests. Some properties of the sequence of requests are given. Finally, an expression for the variance of the search time is obtained.
ISSN:0021-9002
1475-6072
DOI:10.2307/3215222