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

DOI10.1239/jap/1077134682zbMath1093.68029OpenAlexW2119320055MaRDI 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 transformLaplace integralmove-to-front rule

Mathematics Subject Classification ID

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

Related Items (7)

Comparison of subdominant eigenvalues of some linear search schemes ⋮ 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 ⋮ 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 ⋮ The limiting move-to-front search-cost in law of large numbers asymptotic regimes ⋮ SIZE-BIASED PERMUTATION OF DIRICHLET PARTITIONS AND SEARCH-COST DISTRIBUTION

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

This page was built for publication: On the distribution of the search cost for the move-to-front rule with random weights