Optimal list order under partial memory constraints

Suppose that we are given a set of n elements which are to be arranged in some order. At each unit of time a request is made to retrieve one of these elements — the ith being requested with probability P i . We show that the rule which always moves the requested element one closer to the front of the line minimizes the average position of the element requested among a wide class of rules for all probability vectors of the form P 1 = p, P 2 = · ·· = P n = (1 – p )/( n − 1). We also consider the above problem when the decision-maker is allowed to utilize such rules as ‘only make a change if the same element has been requested k times in a row', and show that as k approaches infinity we can do as well as if we knew the values of the P i .