Hostname: page-component-7b7567c8c-fvjsw Total loading time: 0 Render date: 2026-11-16T09:04:41.157Z Has data issue: false hasContentIssue false

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

Published online by Cambridge University Press:  14 July 2016

Eliane R. Rodrigues*
Affiliation:
Universidade de Brasília
*
∗ Present address: Instituto de Matemáticas, UNAM, Area de la Investigación Científica, Circuita Exterior, Ciudad Universitaria, México DF 04510, México.

Abstract

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.

Information

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

Article purchase

Temporarily unavailable