Comparison of subdominant eigenvalues of some linear search schemes |
| |
Authors: | AJ Pryde |
| |
Institution: | aSchool of Mathematical Sciences, Monash University, Victoria 3800, Australia |
| |
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. |
| |
Keywords: | Subdominant eigenvalue Move-to-front Transposition |
本文献已被 ScienceDirect 等数据库收录! |