Limiting search cost distribution for the move-to-front rule with random request probabilities

Javiera Barrera; Thierry Huillet; Christian Paroissin

doi:10.1016/j.orl.2005.09.007

Limiting search cost distribution for the move-to-front rule with random request probabilities

Javiera Barrera
, Thierry Huillet
, Christian Paroissin

Producción científica: Contribución a una revista › Artículo › revisión exhaustiva

4 Citas (Scopus)

Resumen

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.

Idioma original	Inglés
Páginas (desde-hasta)	557-563
Número de páginas	7
Publicación	Operations Research Letters
Volumen	34
N.º	5
DOI	https://doi.org/10.1016/j.orl.2005.09.007
Estado	Publicada - sep. 2006
Publicado de forma externa	Sí

Acceder al documento

10.1016/j.orl.2005.09.007

Citar esto

@article{1e395c17139a4ddfbbd0483a7ed25c9c,

title = "Limiting search cost distribution for the move-to-front rule with random request probabilities",

abstract = "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.",

keywords = "Limiting distribution, Move-to-front, Random discrete distribution, Search cost, Size-biased permutation",

author = "Javiera Barrera and Thierry Huillet and Christian Paroissin",

note = "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.",

year = "2006",

month = sep,

doi = "10.1016/j.orl.2005.09.007",

language = "English",

volume = "34",

pages = "557--563",

journal = "Operations Research Letters",

issn = "0167-6377",

publisher = "Elsevier B.V.",

number = "5",

}

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 - https://www.scopus.com/pages/publications/33746925211

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 -

Limiting search cost distribution for the move-to-front rule with random request probabilities

Resumen

Acceder al documento

Huella

Citar esto