Cornell University Probability Seminar

Spring 2011

Mondays in 406 Malott Hall at 4:00 PM, unless otherwise noted.

January 28 (Friday - 4:00 pm in Malott 251)

Anastasia Raymer, UC Davis
Mixing time of the 15 puzzle

We bound the mixing time of the $L \times L$ version of the 15 Puzzle. A Markov chain on the torus $\mathbb{Z}^2_{L^2}$, referred to as the Loyd process after the claimed inventor of the 15 Puzzle, is defined as follows: Tiles numbered $1,2, \dots, L^2-1$ and one blank tile occupy the vertices of the torus. At each step, the blank tile remains in its current position with probability $1/2$ or transposes with one of its four adjacent neighbors, uniformly at random. While similar to the simple exclusion process, this problem differs in that the particles are not identical, and the states of the Loyd Markov chain are permutations of $S_{L^2}$. We show that order $L^4\, \log^2 L$ steps is sufficient for randomizing the tiles, and that order $L^4 \log L$ steps are necessary. We believe that the lower bound is the correct order of the mixing time.