Premium
On the distribution of search cost for the move‐to‐front rule
Author(s) -
Fill James Allen,
Holst Lars
Publication year - 1996
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/(sici)1098-2418(199605)8:3<179::aid-rsa2>3.0.co;2-v
Subject(s) - computer science , poisson distribution , connection (principal bundle) , distribution (mathematics) , cache , embedding , algorithm , mathematics , statistics , parallel computing , geometry , artificial intelligence , mathematical analysis
A file of records, each with an associated request probability, is dynamically maintained as a serial list. Successive requests are mutually independent. The list is reordered according to the move‐to‐front (MTF) rule: The requested record is moved to the front of the list. We derive the stationary distribution of search cost (=depth of requested item) by embedding in Poisson processes and derive certain finite‐time stochastic ordering results for the MTF chain so embedded. A connection with cache fault probabilities is discussed. We also establish a Schur‐concavity result for stationary expected search cost. © 1996 John Wiley & Sons, Inc.