TY - JOUR
T1 - Limiting search cost distribution for the move-to-front rule with random request probabilities
AU - Barrera, Javiera
AU - Huillet, Thierry
AU - Paroissin, Christian
N1 - Funding Information:
The authors thank support from FONDAP-CONICYT in Applied Mathematics and Millenium Nucleus in Information and Randomness ICM P01-005. J. B. wishes to thank CONICYT National Postgraduate Fellowship Program supporting her Ph.D. The authors also thank their referees for suggested improvements of the original draft.
PY - 2006/9
Y1 - 2006/9
N2 - Consider a list of n files whose popularities are random. The list is updated according to the move-to-front rule. When the induced Markov chain is at equilibrium, we explicitly compute the limiting distribution of the search-cost per item as n tends to infinity. The uniform distribution results in the largest search cost.
AB - Consider a list of n files whose popularities are random. The list is updated according to the move-to-front rule. When the induced Markov chain is at equilibrium, we explicitly compute the limiting distribution of the search-cost per item as n tends to infinity. The uniform distribution results in the largest search cost.
KW - Limiting distribution
KW - Move-to-front
KW - Random discrete distribution
KW - Search cost
KW - Size-biased permutation
UR - http://www.scopus.com/inward/record.url?scp=33746925211&partnerID=8YFLogxK
U2 - 10.1016/j.orl.2005.09.007
DO - 10.1016/j.orl.2005.09.007
M3 - Article
AN - SCOPUS:33746925211
SN - 0167-6377
VL - 34
SP - 557
EP - 563
JO - Operations Research Letters
JF - Operations Research Letters
IS - 5
ER -