✦ LIBER ✦

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

✍ Scribed by Javiera Barrera; Thierry Huillet; Christian Paroissin

Publisher: Elsevier Science
Year: 2006
Tongue: English
Weight: 181 KB
Volume: 34
Category: Article
ISSN: 0167-6377
DOI: 10.1016/j.orl.2005.09.007

No coin nor oath required. For personal study only.

✦ Synopsis

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.

📜 SIMILAR VOLUMES

On the distribution of search cost for t

On the distribution of search cost for the move-to-front rule

✍ James Allen Fill; Lars Holst 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 393 KB 👁 1 views

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