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, 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 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.

Additional Metadata
Journal SIAM Journal on Computing
Citation
Oommen, J, & Hansen, E.R. (E. R.). (1987). LIST ORGANIZING STRATEGIES USING STOCHASTIC MOVE-TO-FRONT AND STOCHASTIC MOVE-TO-REAR OPERATIONS. SIAM Journal on Computing, 16(4), 705–716.