The limiting move-to-front search-cost in law of large numbers asymptotic regimes

Javiera Barrera, Joaquín Fontbona

Research output: Contribution to journalArticlepeer-review

8 Scopus citations


We explicitly compute the limiting transient distribution of the search-cost in the move-to-front Markov chain when the number of objects tends to infinity, for general families of deterministic or random request rates. Our techniques are based on a "law of large numbers for random partitions, " a scaling limit that allows us to exactly compute limiting expectation of empirical functionals of the request probabilities of objects. In particular, we show that the limiting search-cost can be split at an explicit deterministic threshold into one random variable in equilibrium, and a second one related to the initial ordering of the list. Our results ensure the stability of the limiting search-cost under general perturbations of the request probabilities. We provide the description of the limiting transient behavior in several examples where only the stationary regime is known, and discuss the range of validity of our scaling limit.

Original languageEnglish
Pages (from-to)722-752
Number of pages31
JournalAnnals of Applied Probability
Issue number2
StatePublished - Apr 2010
Externally publishedYes


  • Law of large numbers
  • Move-to-front rule
  • Propagation of chaos
  • Search-cost


Dive into the research topics of 'The limiting move-to-front search-cost in law of large numbers asymptotic regimes'. Together they form a unique fingerprint.

Cite this