A New Family of Randomized Algorithms for List Accessing

. Sequential lists are a frequently used data structure for implementing dictionaries. Recently, self-organizing sequential lists have been proposed for "engines" in efficient data compression algorithms. In this paper, we investigate the problem of list accessing from the perspective of competitive analysis. We establish a connection between randomized list accessing algorithms and Markov chains, and present MarkovMove -To-Front, a family of randomized algorithms. To every finite, irreducible Markov chain corresponds a member of the family. The family includes as members well known algorithms such as Move-To-Front, Random-Move-To-Front, Counter, and Random-Reset. First we analyze Markov-Move-To-Front in the standard model, and present upper and lower bounds that depend only on two parameters of the underlying Markov chain. Then we apply the bounds to particular members of the family. The bounds that we get are at least as good as the known bounds. Furthermore, for some algorithms we ..