List Organizing Strategies Using Stochastic Move-to-Front and Stochastic Move-to-Rear Operations
B. John Oommen, Eskil Hansen · SIAM Journal on Computing · 1987
Consider a list of elements $\{ R_1 , \cdots ,R_N \} $ in which the element $R_1 $ is accessed with an (unknown) probability $s_i $. If the cost of accessing $R_i $ is proportional to i (as in sequential search) then it is advantageous if each access is accompanied by a simple reordering operation. This operation is chosen so that ultimately the list will be sorted in the descending order of the access probabilities. In this paper we present two list organizing schemes, the first of which uses bounded memory and the second of which uses memory proportional to the number of elements in the list. Both of the schemes reorder the list by moving only the accessed element. However, as opposed to the schemes discussed in the literature the move operation is performed stochastically in such a way that ultimately no more move operations are performed. When this occurs we say that the scheme has converged. We shall show that: (i) The bounded memory stochastic move-to-front algorithm is expedient, but is always worse than the deterministic move-to-front algorithm. (ii) The linear memory stochastic move-to-rear scheme is optimal, independent of the distribution of the access probabilities. By this we mean that although the list could converge to one of its N! configurations, by suitably updating the probability of performing the move-to-rear operation, the probability of converging to the right arrangement can be made as close to unity as desired.