Return to Colloquia & Seminar listing
Mixing time of the 15 Puzzle
ProbabilitySpeaker: | 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.