An exact formula for the move-to-front rule for self-organizing lists

DOI10.1007/BF02213737zbMath0837.60063MaRDI QIDQ1908208

James Allen Fill

Publication date: 20 May 1996

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

zbMATH Keywords

permutationsMarkov chainseigenvaluesseparationTsetlin libraryconvergence to stationaritymove-to-front ruleself-organizing search

Mathematics Subject Classification ID

Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.) (60J20)

Related Items

Antiduality and Möbius monotonicity: generalized coupon collector problem ⋮ The eigenvalues of hyperoctahedral descent operators and applications to card-shuffling ⋮ The move-to-partner rule for self-organizing task allocation on a linear array ⋮ Comparison of subdominant eigenvalues of some linear search schemes ⋮ Upper Bounds on Mixing Time of Finite Markov Chains ⋮ A Transposition Rule Analysis Based on a Particle Process ⋮ Markov chains on graded posets. Compatibility of up-directed and down-directed transition probabilities ⋮ Eigenvalues of LRU via a linear algebraic approach ⋮ A note on an alternating upper bound for random walks on semigroups ⋮ Markov Chains for Promotion Operators ⋮ Leading the field: fortune favors the bold in Thurstonian choice models ⋮ Edge flipping in graphs ⋮ A combinatorial description of the spectrum for the Tsetlin library and its generalization to hyperplane arrangements ⋮ Limits and rates of convergence for the distribution of search cost under the move-to-front rule ⋮ Generalizations of an expansion formula for top to random shuffles ⋮ Limiting behaviour of the stationary search cost distribution driven by a generalized gamma process ⋮ Combinatorial Markov chains on linear extensions ⋮ The limiting move-to-front search-cost in law of large numbers asymptotic regimes ⋮ Stochastic ranking process with time dependent intensities ⋮ Hypergraph Coloring Games and Voter Models ⋮ Least-recently-used caching with dependent requests ⋮ Critical sizing of LRU caches with dependent requests ⋮ Properties of the promotion Markov chain on linear extensions ⋮ Unnamed Item ⋮ The Move-to-Front Rule: A Case Study for two Perfect Sampling Algorithms ⋮ Optimal strong stationary times for random walks on the chambers of a hyperplane arrangement ⋮ Lumpings of algebraic Markov chains arise from subquotients ⋮ Asymptotic approximation of the move-to-front search cost distribution and least-recently used caching fault probabilities ⋮ Random walks and hyperplane arrangements

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Strong stationary times via a new form of duality
• Stochastic rearrangement rules for self-organizing data structures
• Strong uniform times and finite random walks
• Self-organizing files with dependent accesses
• The heaps process, libraries, and size-biased permutations
• On the matrix occurring in a linear search problem
• Reordering heuristics for routing in communications networks
• Shuffling Cards and Stopping Times
• Self-adjusting binary search trees
• Data compression
• A locally adaptive data compression scheme
• Optimal list order under partial memory constraints
• Exegesis of Self-Organizing Linear Search
• Transience and recurrence of an interesting Markov chain
• On self-organizing sequential search heuristics
• An Account of Self-Organizing Systems
• Heuristics That Dynamically Organize Data Structures
• Analysis of Top To Random Shuffles
• On the transition probabilities of the move-to-front scheme
• On a model for storage and search
• On Serial Files with Relocatable Records
• FINITE AUTOMATA AND MODELS OF SIMPLE FORMS OF BEHAVIOUR
• The stationary distribution of an interesting Markov chain