On the matrix occurring in a linear search problem

DOI10.2307/3214870MaRDI QIDQ3357218zbMATH OpenOpenAlexFDO

Authors Ravindra M. Phatarfod

Publication date 1991

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

Full work available at URL https://doi.org/10.2307/3214870

zbMATH Keywords

cost of retrievaleigenvalueslumpableMarkov chainmatching problemsordering scheme

Mathematics Subject Classification ID

Eigenvalues, singular values, and eigenvectors (15A18) Stochastic matrices (15B51) 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) Applications of queueing theory (congestion, allocation, storage, traffic, etc.) (60K30)

Recommendations

• On the move-to-front scheme with Markov dependent requests
• Multiplicities of eigenvalues of some linear search schemes
• scientific article; zbMATH DE number 970669
• On some multi-request move-to-front heuristics
• MOVE-TO-FRONT RULE FOR ACCESSING SEVERAL RECORDS

Cited in

(35)

• Multiplicities of eigenvalues of some linear search schemes
• Asymptotic approximation of the move-to-front search cost distribution and least-recently used caching fault probabilities
• Random walks and hyperplane arrangements
• Qsym over Sym is free
• Perron eigenvector of the Tsetlin matrix
• The combinatorics of the bar resolution in group cohomology
• An exact formula for the move-to-front rule for self-organizing lists
• A combinatorial description of the spectrum for the Tsetlin library and its generalization to hyperplane arrangements
• Combinatorial Markov chains on linear extensions
• Optimal strong stationary times for random walks on the chambers of a hyperplane arrangement
• Lumpings of algebraic Markov chains arise from subquotients
• Eigenvalues of LRU via a linear algebraic approach
• A note on an alternating upper bound for random walks on semigroups
• scientific article; zbMATH DE number 1270016 (Why is no real title available?)
• Analysis of Top To Random Shuffles
• On the transition probabilities of the move-to-front scheme
• scientific article; zbMATH DE number 1031932 (Why is no real title available?)
• On the move-to-front scheme with Markov dependent requests
• The move-to-partner rule for self-organizing task allocation on a linear array
• The move-to-root rule for self-organizing trees with Markov dependent requests^∗
• Search problems in vector spaces
• Bell numbers, partition moves and the eigenvalues of the random-to-top shuffle in Dynkin types A, B and D
• Markov Chains for Promotion Operators
• Random shuffles on trees using extended promotion
• scientific article; zbMATH DE number 970669 (Why is no real title available?)
• Invariant theory for the free left-regular band and a \(q\)-analogue
• The one-sided cycle shuffles in the symmetric group algebra
• Edge flipping in graphs
• Enumerative theory for the Tsetlin library
• A necessary and sufficient condition for double coset lumping of Markov chains on groups with an application to the random to top shuffle
• Invariant theory for the free left-regular band and a q-analogue
• Properties of the promotion Markov chain on linear extensions
• Comparison of subdominant eigenvalues of some linear search schemes
• r-Qsym is free over Sym
• Functions of random walks on hyperplane arrangements

This page was built for publication: On the matrix occurring in a linear search problem

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