UC Davis Mathematics

Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

Mixing time of the 15 Puzzle

Mathematical Physics & Probability

Speaker: Tasia Raymer, UC Davis
Location: 1147 MSB
Start time: Wed, May 25 2011, 4:10PM

We bound the mixing time of the LxL version of the 15 Puzzle. A Markov chain on the LxL torus, referred to as the Loyd process after the claimed inventor of the 15 Puzzle, is defined as follows: tiles numbered 1,2,...,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 order L^2. We show that order L^4 log 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.