Perfect simulation from the move ahead 1 chain

12/02/2014 - 12:15pm
12/02/2014 - 1:10pm
Mark Huber (CMC)

Suppose that I have a stack of books on my desk. To find a book, I start at the top and work my way down to the desired book. After finding the book, I can move the book one position towards the top of the stack so that it will be slightly easier to find next time. Under the model that all the books are chosen independently, and book i is chosen with probability p_i, this gives rise to a Markov chain called the move ahead 1 chain. Books with relatively large p_i will tend to move to the top of the stack, while books with low p_i will tend to stay in the bottom. For this reason, this is called a self-organizing list, and provides a simple model for database organization. After many steps in this chain, the state will be in a long run distribution on permutations of the objects in the stack. In order to estimate quantities such as the expected time needed to access an object, it is necessary to be able to draw random samples from this distribution over permutations. In this talk I'll discuss a new method for doing so and prove that it runs in linear time as long as the p_i (when ordered) decrease sufficiently quickly.

Mudd Science Library 126, Pomona College