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

DOI10.1007/BF02213737MaRDI QIDQ1908208zbMATH OpenFDO

Authors James Allen Fill

Publication date 20 May 1996

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

zbMATH Keywords

permutationseigenvaluesMarkov chainsseparationTsetlin libraryconvergence to stationaritymove-to-front ruleself-organizing search

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 795110
• Deterministic optimal and expedient move-to-rear list organizing strategies
• scientific article; zbMATH DE number 4049074
• List Organizing Strategies Using Stochastic Move-to-Front and Stochastic Move-to-Rear Operations
• Optimality of move-to-front for self-organizing data structures with locality of references
• Stochastic rearrangement rules for self-organizing data structures
• The Move-to-Front Rule for Multiple Lists
• scientific article; zbMATH DE number 480526

Cites work

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

Cited in

(34)

• scientific article; zbMATH DE number 480526 (Why is no real title available?)
• A note on an alternating upper bound for random walks on semigroups
• A Transposition Rule Analysis Based on a Particle Process
• Optimal strong stationary times for random walks on the chambers of a hyperplane arrangement
• scientific article; zbMATH DE number 795110 (Why is no real title available?)
• Edge flipping in graphs
• A combinatorial description of the spectrum for the Tsetlin library and its generalization to hyperplane arrangements
• Comparison of subdominant eigenvalues of some linear search schemes
• Lumpings of algebraic Markov chains arise from subquotients
• Limiting behaviour of the stationary search cost distribution driven by a generalized gamma process
• Limits and rates of convergence for the distribution of search cost under the move-to-front rule
• Least-recently-used caching with dependent requests
• Markov chains on graded posets. Compatibility of up-directed and down-directed transition probabilities
• Self-organizing lists and independent references: A statistical synergy
• The eigenvalues of hyperoctahedral descent operators and applications to card-shuffling
• Critical sizing of LRU caches with dependent requests
• Properties of the promotion Markov chain on linear extensions
• Functional central limit theorem for tagged particle dynamics in stochastic ranking process with space-time dependent intensities
• Upper Bounds on Mixing Time of Finite Markov Chains
• Antiduality and Möbius monotonicity: generalized coupon collector problem
• Random walks and hyperplane arrangements
• Combinatorial Markov chains on linear extensions
• Hypergraph Coloring Games and Voter Models
• The Move-to-Front Rule: A Case Study for two Perfect Sampling Algorithms
• The move-to-partner rule for self-organizing task allocation on a linear array
• scientific article; zbMATH DE number 4155864 (Why is no real title available?)
• The one-sided cycle shuffles in the symmetric group algebra
• Asymptotic approximation of the move-to-front search cost distribution and least-recently used caching fault probabilities
• Generalizations of an expansion formula for top to random shuffles
• Markov Chains for Promotion Operators
• Eigenvalues of LRU via a linear algebraic approach
• The limiting move-to-front search-cost in law of large numbers asymptotic regimes
• Stochastic ranking process with time dependent intensities
• Leading the field: fortune favors the bold in Thurstonian choice models

This page was built for publication: An exact formula for the move-to-front rule for self-organizing lists

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1908208)