Mixing time of the fifteen puzzle (Q508464): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Set OpenAlex properties. |
||
(3 intermediate revisions by 2 users not shown) | |||
Property / reviewed by | |||
Property / reviewed by: Andrew R. Wade / rank | |||
Property / reviewed by | |||
Property / reviewed by: Andrew R. Wade / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2282906890 / rank | |||
Normal rank |
Latest revision as of 11:32, 30 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Mixing time of the fifteen puzzle |
scientific article |
Statements
Mixing time of the fifteen puzzle (English)
0 references
7 February 2017
0 references
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)].
0 references
Markov chain
0 references
fifteen puzzle
0 references
mixing time
0 references
interchange process
0 references