A counterexample to a conjecture on optimal list ordering

Abstract

A number of items are arranged in a line. At each unit of time one of the items is requested, the i th being requested with probability P_i. We consider rules which reorder the items between successive requests in a fashion which depends only on the position in which the most recently requested item was found. It has been conjectured that the rule which always moves the requested item one closer to the front of the line minimizes the average position of the requested item. An example with six items shows that the conjecture is false.