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

2005/06/17 by Javiera Barrera, Barrera, Javiera, Thierry Huillet +3
Mathematics · #68P10 #AMS 2000 Classification: 68W40 #FOS: Mathematics #Probability (math.PR) #math.PR #msc:2000 #msc:68P10 #msc:68W40

paper · pdf · doi:10.48550/arxiv.math/0506343

move-to-front, search cost, random discrete distribution, limiting distribution, size biased permutation

arxiv created 2005/06/17 · arxiv updated 2009/12/01

Abstract

Consider a list of n files whose popularities are random. These files are updated according to the move-to-front rule and we consider the induced Markov chain at equilibrium. We give the exact limiting distribution of the search-cost per item as n tends to infinity. Some examples are supplied.

Related

• Limiting behavior of the search cost distribution for the move-to-front rule in the stable case
• Hydrodynamic limit of move-to-front rules and search cost probabilities
• Limiting behaviour of the stationary search cost distribution driven by a generalized gamma process
• Expanding on Repeated Consumer Search Using Multi-Armed Bandits and Secretaries
• Minimizing the Profligacy of Searches with Reset