Deterministic optimal and expedient move-to-rear list organizing strategies

AbstractLet R = {R1,R2,…,RN} be a list of elements in which R1 is accessed with an (unknown) probabilitys1. To minimize the cost of accessing the elements, it is advantageous if the elements are sorted in descending order of the access probabilities. Attempts to achieve this have been made in which a simple list reordering operation is performed on every access. We present two simple self-organizing strategies. The strategies are deterministic and absorbing in their Markovian representation and are completely counter-intuitive, in that they are of a Move-to-Rear (MTR) flavour. Whereas the first of the schemes requires linear space (space proportional to the number of elements in the list), the second requires only constant space. We show that the former 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 performing the move-to-rear operation, the probability of converging to the right arrangement can be made as close to unity as desired. The second scheme requiring constant space is shown to be expedient. We conjecture its optimality