Optimality of move-to-front

page still to be improved !!

Optimality of move-to-front for self-organizing data structures with locality of references.

Annals of Applied Probability Vol. 3, No. 4, 1993, 1219-1240 (ps.gz 94Ko)
Between 1975 and 1985, there has been a host of studies concerning self organizing data structures and the move-to-front rule, in computer science (Rivest, Konneker & Varol, Kapoor & Reingold, Hofri & Shachnai, Hendricks, Chung & al., Bitner, Bentley & McGeoch, Chong & Lam, Aven & al.). Most of them compare different rules, such as transpose, with respect to the average search cost or to amortized cost. In these studies, it is often mentioned that the assumption of independence of successive requests of keys should be relaxed, and that the (Markovian) dependence should assume the form of a locality phenomenon (Tenenbaum & Nemes, Sleator & Tarjan, Knuth, Hofri & Shachnai, Bentley & McGeoch). In this setting, the move-to-front rule is considered to be close to optimal, if not optimal. The aim of this paper is to give a mathematical basis to this general belief.
Independently, Letac, Dies, Kowalska, led more theoretical studies on recurrence, transience, explicit computations of the stationary distribution, ... in the case of independent requests (see also the more recent papers by Dobrow & Fill, Phatarfod). Since 1993, the Markovian case has also been studied by Dobrow, Lam & al, Phatarfod & al, but these papers do not deal with average cost comparison, or average cost optimality.
To compare average cost of different rules is a challenge in the independent case, where the more striking result is obtained by Rivest, who was able to give a general closed form expression of the average search cost for transpose as well as for move-to-front, and to prove that transpose is more efficient than move-to-front. There are beautiful papers about the average search cost of move-to-front in the Markovian case (Lam & al, Dobrow), but there is a miracle about move-to-front (it is lumpable), and this miracle will not repeat for other rules, for instance transpose: a Rivest-like result seems out of reach in the Markovian case.
In this paper, we evade this difficulty with the help of the Bellman optimality equation of stochastic dynamic programming: it allows to prove that move-to-front has eventually the minimal average search cost among all on-line rules, without computing the average search cost of the other rules. The counterpart is that we need to know more about the move-to-front rule, than simply its average search cost (we need also to compute v(x,m), that denotes some kind of starting costs, as explained page 1222 of this paper ). In this paper , we give a closed form expression of the solution v(x,m) of the Bellman optimality equation for some matrices P whose symmetry group is rich enough (see Theorem 3, Section 9, and also State-transitive Markov processes and random walks on groups C.-R.-Acad.-Sci.-Paris-Ser.-I-Math. 312 (1991), no. 3, 291--296 here ) and we deduce the optimality of move-to-front for these matrices.
In the other hand, though no general solution of the Bellman optimality equation is available, we obtain nevertheless, using coupling arguments, some geometric properties of the class f* of stochastic matrices P such that move-to-front is optimal, something like "f* is starshaped with respect to the unit matrix" (see Theorem 1 & 2, for more precise statements). Roughly speaking, the idea is that if we replace P by aI+(1-a)P, then the locality phenomenon will be more pronounced. Thus, if P belongs to f*, then aI+(1-a)P should belong to f* too. As a conclusion, Theorems 1 and 2 bear out the usual explanation of optimality of move-to-front by a locality phenomenon. A complete description of f* remains open: maybe recent advances of Dobrow, or Phatarfod & al., will allow to go further in this direction.