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

DOI10.1016/j.orl.2005.09.007zbMath1142.68621arXivmath/0506343OpenAlexW2243361254MaRDI QIDQ2480054

Christian Paroissin, Javiera Barrera, Thierry E. Huillet

Publication date: 28 March 2008

Published in: Operations Research Letters (Search for Journal in Brave)

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

zbMATH Keywords

limiting distributionsize-biased permutationrandom discrete distributionsearch costmove-to-front

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Searching and sorting (68P10) Combinatorial probability (60C05) Data structures (68P05) Information storage and retrieval of data (68P20)

Related Items (4)

Limiting behavior of the search cost distribution for the move-to-front rule in the stable case ⋮ Limiting behaviour of the stationary search cost distribution driven by a generalized gamma process ⋮ The limiting move-to-front search-cost in law of large numbers asymptotic regimes ⋮ Functions of random walks on hyperplane arrangements

Cites Work

• 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
• The heaps process, libraries, and size-biased permutations
• 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
• On Serial Files with Relocatable Records
• FINITE AUTOMATA AND MODELS OF SIMPLE FORMS OF BEHAVIOUR
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Limiting search cost distribution for the move-to-front rule with random request probabilities