On the distribution of the search cost for the move-to-front rule with random weights

DOI10.1239/jap/1077134682zbMath1093.68029MaRDI QIDQ4819452

Javiera Barrera, Christian Paroissin

Publication date: 24 September 2004

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

Full work available at URL: https://doi.org/10.1239/jap/1077134682

zbMATH Keywords

Laplace transform; Laplace integral; move-to-front rule

Mathematics Subject Classification ID

68W40: Analysis of algorithms

68P10: Searching and sorting

60C05: Combinatorial probability

44A10: Laplace transform

68P05: Data structures

68P20: Information storage and retrieval of data

Related Items

SIZE-BIASED PERMUTATION OF DIRICHLET PARTITIONS AND SEARCH-COST DISTRIBUTION, A Transposition Rule Analysis Based on a Particle Process, Limiting behavior of the search cost distribution for the move-to-front rule in the stable case, Comparison of subdominant eigenvalues of some linear search schemes, The limiting move-to-front search-cost in law of large numbers asymptotic regimes, Limiting behaviour of the stationary search cost distribution driven by a generalized gamma process, Limiting search cost distribution for the move-to-front rule with random request probabilities

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
• On the optimality of the counter-scheme for dynamic linear lists
• From shuffling cards to walking around the building: An introduction to modern Markov chain theory
• Birthday paradox, coupon collectors, caching algorithms and self- organizing search
• Asymptotics for the random coupon collector problem
• Asymptotic approximation of the move-to-front search cost distribution and least-recently used caching fault probabilities
• Extreme value distributions for random coupon collector and birthday problems
• Random discrete distributions derived from self-similar random sets
• The heaps process, libraries, and size-biased permutations
• On Serial Files with Relocatable Records
• The stationary distribution of an interesting Markov chain