Mixing time of the fifteen puzzle (Q508464)

Let \(G_n = \mathbb{Z}_n^2\) be the \(n \times n\) discrete torus. The authors introduce and study the \textit{Loyd process}, which is a Markov chain on particle-hole configurations on \(G_n\), inspired by the so-called \textit{fifteen puzzle} of Sam Loyd. In a configuration of \(G_n\), the tokens \(\{ 1,2 ,\dots, n^2 -1 \}\), plus a single \textit{hole}, are assigned to the \(n^2\) vertices of \(G_n\). A step of the Loyd process is such that with probability \(1/2\) a vertex adjacent to the hole is chosen uniformly at random, and the places of the hole and the token at the chosen vertex are swapped; with probability \(1/2\) the configuration is unchanged. The authors show that the total-variation mixing time of the Loyd process on \(G_n\) is bounded above and below by constant multiples of \(n^4 \log n\). For the proof of the upper bound, the authors use comparison techniques for random walks on groups [\textit{P. Diaconis} and \textit{L. Saloff-Coste}, Ann. Probab. 21, No. 4, 2131--2156 (1993; Zbl 0790.60011)] and compare the Loyd process, via three intermediate Markov chains, to shuffling by random transpositions. The proof of the lower bound in based on \textit{D. B. Wilson}'s method [Ann. Appl. Probab. 14, No. 1, 274--325 (2004; Zbl 1040.60063)].