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

DOI10.1016/j.orl.2005.09.007zbMath1142.68621arXivmath/0506343MaRDI 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 distribution; size-biased permutation; random discrete distribution; search cost; move-to-front

Mathematics Subject Classification ID

68W40: Analysis of algorithms

68P10: Searching and sorting

60C05: Combinatorial probability

68P05: Data structures

68P20: Information storage and retrieval of data

Related Items

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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
• 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