Mixing time of the fifteen puzzle
type: Item
instance of: scholarly article
title: Mixing time of the fifteen puzzle
zbMATH Open document ID: 1360.60136
DOI: 10.1214/16-EJP11
author: Ben Morris
author: Anastasia Raymer
published in: Electronic Journal of Probability
publication date: 2017-02-07T00:00:00Z
full work available at URL: https://projecteuclid.org/euclid.ejp/1485831705
review text: 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)].
Mathematics Subject Classification ID: 60J10
zbMATH DE Number: 6681511
zbMATH Keywords: Markov chain
zbMATH Keywords: fifteen puzzle
zbMATH Keywords: mixing time
zbMATH Keywords: interchange process
reviewed by: Andrew R. Wade
MaRDI profile type: Publication
OpenAlex ID: W2282906890
description: scientific article; zbMATH DE number 6681511