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

DOI10.1007/BF02213737zbMATH Open0837.60063MaRDI QIDQ1908208FDOQ1908208

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)

Cites Work

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

Cited In (34)

• Title not available (Why is that?)
• A Transposition Rule Analysis Based on a Particle Process
• Optimal strong stationary times for random walks on the chambers of a hyperplane arrangement
• A note on an alternating upper bound for random walks on semigroups
• Title not available (Why is that?)
• Edge flipping in graphs
• A combinatorial description of the spectrum for the Tsetlin library and its generalization to hyperplane arrangements
• Lumpings of algebraic Markov chains arise from subquotients
• Comparison of subdominant eigenvalues of some linear search schemes
• 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
• Markov chains on graded posets. Compatibility of up-directed and down-directed transition probabilities
• Least-recently-used caching with dependent requests
• Critical sizing of LRU caches with dependent requests
• Self-organizing lists and independent references: A statistical synergy
• The eigenvalues of hyperoctahedral descent operators and applications to card-shuffling
• Properties of the promotion Markov chain on linear extensions
• 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
• Title not available (Why is that?)
• 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
• Title not available (Why is that?)
• Leading the field: fortune favors the bold in Thurstonian choice models
• The limiting move-to-front search-cost in law of large numbers asymptotic regimes
• Stochastic ranking process with time dependent intensities

Recommendations

• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• List Organizing Strategies Using Stochastic Move-to-Front and Stochastic Move-to-Rear Operations 👍 👎
• Deterministic optimal and expedient move-to-rear list organizing strategies 👍 👎
• Stochastic rearrangement rules for self-organizing data structures 👍 👎
• Optimality of move-to-front for self-organizing data structures with locality of references 👍 👎
• The Move-to-Front Rule for Multiple Lists 👍 👎

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)