Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

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.