Mixing time of the fifteen puzzle (Q508464): Difference between revisions
From MaRDI portal
Created a new Item |
Set OpenAlex properties. |
||
(5 intermediate revisions by 4 users not shown) | |||
Property / 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)]. | |||
Property / 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)]. / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 60J10 / rank | |||
Normal rank | |||
Property / zbMATH DE Number | |||
Property / zbMATH DE Number: 6681511 / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
Markov chain | |||
Property / zbMATH Keywords: Markov chain / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
fifteen puzzle | |||
Property / zbMATH Keywords: fifteen puzzle / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
mixing time | |||
Property / zbMATH Keywords: mixing time / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
interchange process | |||
Property / zbMATH Keywords: interchange process / rank | |||
Normal 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 | |||
links / mardi / name | links / mardi / name | ||
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