Abstract

Markov chains are a basic tool of simulation and optimisation in applied mathematics and statistics. One simple, widely-used chain is the move-to-front rule for dynamic storage allocation: suppose one repeatedly makes independent requests for a random file amongst a list, searching for the necessary file from the front of the list at each request. One method of reducing the average search time is to return each requested file to the front, so that frequently-requested files are more likely to be near the front. To investigate whether this scheme is efficient, one wishes to calculate the likely order of the files in the long run (the stationary distribution), and how many requests it takes to put the system into this long run state (the convergence rate). We illustrate how a new connection to Hopf algebras can shed light on these two important questions for many similar chains on lists all at once, as well as for analogous processes on trees, graphs and numerous other objects.