Comparison of subdominant eigenvalues of some linear search schemes

DOI10.1016/j.laa.2009.05.008zbMath1181.15013OpenAlexW2014215920MaRDI QIDQ840641

Alan J. Pryde

Publication date: 14 September 2009

Published in: Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.laa.2009.05.008

zbMATH Keywords

transition probability matrixMarkov chaintranspositionsubdominant eigenvaluelinear search schemesmove-to-frontRayleigh-Ritz theorem

Mathematics Subject Classification ID

Searching and sorting (68P10) Interacting random processes; statistical mechanics type models; percolation theory (60K35) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Eigenvalues, singular values, and eigenvectors (15A18)

Cites Work

• An exact formula for the move-to-front rule for self-organizing lists
• On the matrix occurring in a linear search problem
• The persistent-access-caching algorithm
• Matrix Analysis
• On self-organizing sequential search heuristics
• An Account of Self-Organizing Systems
• On the move-to-front scheme with Markov dependent requests
• On the distribution of the search cost for the move-to-front rule with random weights
• A Transposition Rule Analysis Based on a Particle Process

This page was built for publication: Comparison of subdominant eigenvalues of some linear search schemes