Comparison of subdominant eigenvalues of some linear search schemes

Alan James Pryde

Research output: Contribution to journalArticleResearchpeer-review

Abstract

The subdominant eigenvalue of the transition probability matrix of a Markov chain is a determining factor in the speed of transition of the chain to a stationary state. However, these eigenvalues can be difficult to estimate in a theoretical sense. In this paper we revisit the problem of dynamically organizing a linear list. Items in the list are selected with certain unknown probabilities and then returned to the list according to one of two schemes: the move-to-front scheme or the transposition scheme. The eigenvalues of the transition probability matrix Q of the former scheme are well-known but those of the latter T are not. Nevertheless the transposition scheme gives rise to a reversible Markov chain. This enables us to employ a generalized Rayleigh-Ritz theorem to show that the subdominant eigenvalue of T is at least as large as the subdominant eigenvalue of Q.
Original languageEnglish
Pages (from-to)1439 - 1442
Number of pages4
JournalLinear Algebra and Its Applications
Volume431
Issue number9
Publication statusPublished - 2009

Cite this