AN EXACT FORMULA FOR THE MOVE-TO-FRONT RULE FOR SELF-ORGANIZING LISTS

A collection of items (e.g., books), each with an associated weight (o r popularity), is arranged in a row. At each unit of time an item is r emoved with probability proportional to its weight and replaced at the left end of the row. This move-to-front rule gives a Markov chain on permutations often known as the Tsetlin library. We derive an exact an d tractable formula for the probability of any permutation after any n umber of moves. From the formula we read off previously studied quanti ties of interest associated with the chain, such as the stationary dis tribution and eigenvalues. Measuring discrepancy from stationarity by separation, we use the formula to find the initial arrangement giving the slowest convergence to stationarity. The time to stationarity in t his case is a convolution of geometric random variables which we analy ze for three natural choices of weights. We also assess the time requi red for an important functional, namely, expected search cost, to appr oach its stationary value.