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

DOI10.1214/09-AAP635zbMATH Open1204.60005arXivmath/0611882OpenAlexW1990305432MaRDI QIDQ968782FDOQ968782

Authors: Javiera Barrera, Joaquin Fontbona 

Publication date: 6 May 2010

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

Abstract: 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.

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

Recommendations

• 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
• Limits and rates of convergence for the distribution of search cost under the move-to-front rule
• On the distribution of the search cost for the move-to-front rule with random weights
• Publication:4885223

zbMATH Keywords

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

Mathematics Subject Classification ID

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

Cites Work

• Asymptotic Statistics
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• 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
• The persistent-access-caching algorithm
• Title not available (Why is that?)
• Limits and rates of convergence for the distribution of search cost under the move-to-front rule
• Limiting search cost distribution for the move-to-front rule with random request probabilities
• 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
• A convergence theorem for symmetric functionals of random partitions

Cited In (7)

• Limiting behaviour of the stationary search cost distribution driven by a generalized gamma process
• Limits and rates of convergence for the distribution of search cost under the move-to-front rule
• Limiting search cost distribution for the move-to-front rule with random request probabilities
• Functional central limit theorem for tagged particle dynamics in stochastic ranking process with space-time dependent intensities
• Optimal timer-based caching policies for general arrival processes
• Limiting behavior of the search cost distribution for the move-to-front rule in the stable case
• Title not available (Why is that?)

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q968782)