The Shelf of Binders

Part A: Transpose can be made to shuffle two binders forever

Ask for binder 5, then 4, then 5, then 4. Transpose swaps the requested binder with the one in front of it, so 5 and 4 keep trading places at the back of the shelf. Every request costs 5, the most possible. Move-to-front pays 5 once, 5 again for binder 4, and then 2 for every request after that: 30 instead of 60 on twelve requests.

Part B: move-to-front's cruellest sequence

Always asking for the last binder costs move-to-front 5 every time, and it asks for the binders in a cycle, each equally often. Any fixed order then pays $(1+2+3+4+5)/5=3$ per request on average, so the ratio is 5/3. With $k$ binders it is $2k/(k+1)$, just under 2.

Part C: why move-to-front stays within twice the best fixed order

Bentley and McGeoch's argument looks at one pair of binders $x$ and $y$ at a time, where the best fixed order puts $x$ before $y$. The cost of reaching past a binder splits into these pairs. The best fixed order pays for the pair whenever $y$ is requested. Move-to-front pays for it in two cases. Either $y$ is requested while $x$ is in front of it, which the fixed order pays for too. Or $x$ is requested while $y$ is in front of it, and that can only happen if $y$ was requested since the last request for $x$. So the second kind of payment is at most the number of requests for $y$, and move-to-front pays at most twice what the fixed order pays on every pair, plus a start-up cost from the initial order.

On the grader's sequences with 8 binders, move-to-front paid at most 1.78 times the best fixed order (on the sequence that always asks for its last binder). Transpose paid 5.33 times on two of them, and never moving paid 8 times.

Frequency count also passes part C. Against a fixed order it is reasonable, because it converges to that order. Its weakness shows only against a rival who can rearrange too (part D).

Going further

• Against a rival who can rearrange. Sleator and Tarjan proved that move-to-front pays at most twice what any algorithm pays, including one that knows the future and rearranges at will. That paper started competitive analysis. Transpose and frequency count have no such guarantee.
• Randomization helps. The randomized rule BIT reaches $7/4$, COMB reaches $1.6$, and no randomized rule can beat $1.5$.
• Splay trees are move-to-front for search trees. Whether they are within a constant of the best dynamic tree is the dynamic optimality conjecture (Splay Trees).

References

1. J. L. Bentley, C. C. McGeoch. Amortized analyses of self-organizing sequential search heuristics. Communications of the ACM 28(4), 1985.
2. D. D. Sleator, R. E. Tarjan. Amortized efficiency of list update and paging rules. Communications of the ACM 28(2), 1985.
3. N. Reingold, J. Westbrook, D. D. Sleator. Randomized competitive algorithms for the list update problem. Algorithmica 11, 1994.
4. S. Albers, B. von Stengel, R. Werchner. A combined BIT and TIMESTAMP algorithm for the list update problem. Information Processing Letters 56(3), 1995.
5. B. Teia. A lower bound for randomized list update algorithms. Information Processing Letters 47(1), 1993.