Hydrodynamic limit of move-to-front rules and search cost probabilities

2009/08/22 by Kumiko Hattori, Hattori, Kumiko, Tetsuya Hattori +1 · 1 citation
Computer Science · Decision Sciences · #35C05 #60K35 #68P10 #82C22 #Advanced Data Storage Technologies #Auction Theory and Applications #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Optimization and Search Problems #Probability (math.PR)

paper · pdf · doi:10.48550/arxiv.0908.3222

openalex publication_date 2009/08/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We study a hydrodynamic limit approach to move-to-front rules, namely, a scaling limit as the number of items tends to infinity, of the joint distribution of jump rate and position of items. As an application of the limit formula, we present asymptotic formulas on search cost probability distributions, applicable for general jump rate distributions.

Cited by

• Approximation of LRU Caches Miss Rate: Application to Power-law Popularities

Related

• Limiting behavior of the search cost distribution for the move-to-front rule in the stable case
• Limiting search cost distribution for the move-to-front rule with random request probabilities
• Limiting behaviour of the stationary search cost distribution driven by a generalized gamma process
• Hydrodynamic limit of order book dynamics
• Minimizing the Profligacy of Searches with Reset