? Applied Probability Trust 1982 A COUNTEREXAMPLE TO A CONJECTURE ON OPTIMAL LIST ORDERING

A number of items are arranged in a line. At each unit of time one of the items is requested, the ith being requested with probability P,. 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. OPTIMAL LIST ORDER; MEMORY CONSTRAINTS; TRANSPOSITION RULE 1. A conjecture on optimal list ordering In modeling the storage of computer files, Rivest (1976) considered the problem of finding an optimal rule for self-ordering a line of items, e,---, en. At each unit of time a request is made (independently of previous requests) to retrieve one of the items: the ith being requested with probability Pi, P,> 0, I P, = 1. The retrieval cost is equal to the position of the requested item in the line. Items may be reordered without cost between requests, but it is not possible to remember the frequencies with which the different items have been requested in the past. Therefore any reordering which is made between two successive requests, must be made using a no-memory rule which reorders the items in a fashion depending only on the position in which the most recently requested item was found. Rivest considered the transposition rule which transposes the requested item with the item which is one position closer to the front of the line. He showed that for all probability vectors P = (P,---, Pn) the transposition rule has a smalle