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

DOI10.1214/09-AAP635zbMath1204.60005arXivmath/0611882OpenAlexW1990305432MaRDI QIDQ968782

Javiera Barrera, Joaquin Fontbona

Publication date: 6 May 2010

Published in: The Annals of Applied Probability (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/math/0611882

zbMATH Keywords

asymptotic distributionpropagation of chaosmove-to-front rulesearch-cost process

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Searching and sorting (68P10) Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.) (60J20) Convergence of probability measures (60B10)

Related Items (3)

Optimal timer-based caching policies for general arrival processes ⋮ Limiting behaviour of the stationary search cost distribution driven by a generalized gamma process ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Limits and rates of convergence for the distribution of search cost under the move-to-front rule
• Birthday paradox, coupon collectors, caching algorithms and self- organizing search
• Asymptotic approximation of the move-to-front search cost distribution and least-recently used caching fault probabilities
• An exact formula for the move-to-front rule for self-organizing lists
• Limiting search cost distribution for the move-to-front rule with random request probabilities
• The persistent-access-caching algorithm
• A convergence theorem for symmetric functionals of random partitions
• Asymptotic Statistics
• SIZE-BIASED PERMUTATION OF DIRICHLET PARTITIONS AND SEARCH-COST DISTRIBUTION
• On the distribution of the search cost for the move-to-front rule with random weights

This page was built for publication: The limiting move-to-front search-cost in law of large numbers asymptotic regimes