An exact formula for the move-to-front rule for self-organizing lists
From MaRDI portal
Publication:1908208
DOI10.1007/BF02213737zbMath0837.60063MaRDI QIDQ1908208
Publication date: 20 May 1996
Published in: Journal of Theoretical Probability (Search for Journal in Brave)
permutations; Markov chains; eigenvalues; separation; Tsetlin library; convergence to stationarity; move-to-front rule; self-organizing search
60J10: Markov chains (discrete-time Markov processes on discrete state spaces)
60J20: Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.)
Related Items
The move-to-partner rule for self-organizing task allocation on a linear array, The Move-to-Front Rule: A Case Study for two Perfect Sampling Algorithms, A Transposition Rule Analysis Based on a Particle Process, Critical sizing of LRU caches with dependent requests, Stochastic ranking process with time dependent intensities, Edge flipping in graphs, Limits and rates of convergence for the distribution of search cost under the move-to-front rule, Least-recently-used caching with dependent requests, Comparison of subdominant eigenvalues of some linear search schemes, The limiting move-to-front search-cost in law of large numbers asymptotic regimes, Asymptotic approximation of the move-to-front search cost distribution and least-recently used caching fault probabilities, Random walks and hyperplane arrangements, A combinatorial description of the spectrum for the Tsetlin library and its generalization to 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
