Cost comparison of a spectrum of self-organizing rules

Consider the following self-organizing rule called POS(i): after a book in the jth position of a shelf is borrowed, it is moved up one position if j ≦ i, and is moved to the ith position if j > i. This is a family of move-forward rules, with POS(1) being the move-to-front rule and POS(n–1) being the transposition rule where n is the number of books to be organized. We derive explicitly the stationary distribution under the POS(i) rule and show that its search cost compares favorably with that of move-to-front rule under any book access probabilities p1, p2, ..., pn.