On the matrix occurring in a linear search problem

DOI10.2307/3214870zbMath0731.60062OpenAlexW2042465999MaRDI QIDQ3357218

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

eigenvaluesMarkov chainmatching problemscost of retrievallumpableordering scheme

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

Related Items (25)

The combinatorics of the bar resolution in group cohomology ⋮ The move-to-partner rule for self-organizing task allocation on a linear array ⋮ Comparison of subdominant eigenvalues of some linear search schemes ⋮ An exact formula for the move-to-front rule for self-organizing lists ⋮ Analysis of Top To Random Shuffles ⋮ \(r\)-Qsym is free over Sym ⋮ Eigenvalues of LRU via a linear algebraic approach ⋮ Invariant theory for the free left-regular band and a \(q\)-analogue ⋮ A note on an alternating upper bound for random walks on semigroups ⋮ Markov Chains for Promotion Operators ⋮ Qsym over Sym is free ⋮ Random shuffles on trees using extended promotion ⋮ Edge flipping in graphs ⋮ The move-to-root rule for self-organizing trees with Markov dependent requests^∗ ⋮ A combinatorial description of the spectrum for the Tsetlin library and its generalization to hyperplane arrangements ⋮ Bell numbers, partition moves and the eigenvalues of the random-to-top shuffle in Dynkin types A, B and D ⋮ Combinatorial Markov chains on linear extensions ⋮ Functions of random walks on hyperplane arrangements ⋮ Properties of the promotion Markov chain 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 ⋮ 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 ⋮ Perron eigenvector of the Tsetlin matrix

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