{"entities":{"Q508464":{"pageid":510231,"ns":120,"title":"Item:Q508464","lastrevid":62364468,"modified":"2026-04-11T05:35:11Z","type":"item","id":"Q508464","labels":{"en":{"language":"en","value":"Mixing time of the fifteen puzzle"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6681511"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q508464$7B2C2E4F-F380-4446-A3F4-D8BB375E7A14","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"27dfbd193efbab34f206d65e843658cfd77a47db","datavalue":{"value":{"text":"Mixing time of the fifteen puzzle","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q508464$492B7891-076B-49A2-9031-81967173415B","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"fc1b357adf0cd8bd5b37b4f052ff52f6a64c17c4","datavalue":{"value":"1360.60136","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q508464$C34EC5BE-A6EC-4851-9DE5-2EEA437BE5F5","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"7b136ca17ce4a88636b4ec03110735b47403e1b3","datavalue":{"value":"10.1214/16-EJP11","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q508464$470A29C6-7BA4-46C5-AF72-343D668F2D78","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"09e3c3570e969c9c4fb50aa5650f9159270e5f8d","datavalue":{"value":{"entity-type":"item","numeric-id":508462,"id":"Q508462"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q508464$BA9D6BD9-E135-4F27-86D8-08B72C0561CE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"70ba6d17f8ffa8e9fcacdf83b32888e9c8ae3c91","datavalue":{"value":{"entity-type":"item","numeric-id":508463,"id":"Q508463"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q508464$7EF14C26-83BC-4992-9DB2-5A63B99800EA","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"8e07b2886c3cba62bc712a97c290cffae44ef34d","datavalue":{"value":{"entity-type":"item","numeric-id":187915,"id":"Q187915"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q508464$181F9E09-A870-42F9-99F8-950F6EF4C95F","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"f7f5598da38e5abc7c85a2d1789026ae36e393d1","datavalue":{"value":{"time":"+2017-02-07T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q508464$FF4D5688-8A27-418A-BA80-A7452AEE44EE","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"831c00ce53d29e11f4ab59e80cbd06012b91a04e","datavalue":{"value":"https://projecteuclid.org/euclid.ejp/1485831705","type":"string"},"datatype":"url"},"type":"statement","id":"Q508464$2830DD46-564E-424C-870D-EC18A23E1A4E","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"10dcbcf3172024b6be0ca061a0e2130d9ae6daf0","datavalue":{"value":"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)].","type":"string"},"datatype":"string"},"type":"statement","id":"Q508464$A470FA3B-2118-489C-89B8-1D74404C83A3","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"1cdf15533e26fc0c4c2e22d28e655c364dfe77a6","datavalue":{"value":"60J10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q508464$C986CE87-90FD-43AA-B7F0-C39A1BDD79DE","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"b2455ca0443d35b2caada4c30d705890adc0eadc","datavalue":{"value":"6681511","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q508464$26D3EB62-EE5C-443D-9A09-DBFDD4F469FD","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"397d9252ef89819a92633d8502b4000f6e56c083","datavalue":{"value":"Markov chain","type":"string"},"datatype":"string"},"type":"statement","id":"Q508464$9CFBFEFC-3161-40D0-B91D-2D7E5F80F9C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b1e005efb92c89be5725467493cae2b8e7c86e30","datavalue":{"value":"fifteen puzzle","type":"string"},"datatype":"string"},"type":"statement","id":"Q508464$7CC2454C-F8D1-4847-8E8A-DD171F7FA2CA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"06a0ded343c085005653a31a579d4ce087df5055","datavalue":{"value":"mixing time","type":"string"},"datatype":"string"},"type":"statement","id":"Q508464$DB72A43C-C9F1-431A-A8E5-21FEC6F54B7F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ff92df125462208b7b2468f811dd00c7d6621f09","datavalue":{"value":"interchange process","type":"string"},"datatype":"string"},"type":"statement","id":"Q508464$80C8F104-068D-4360-9502-F46BEA7B3556","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"5f1d94592252aa869822dc5e36ade0b0e4d1ca8b","datavalue":{"value":{"entity-type":"item","numeric-id":456206,"id":"Q456206"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q508464$FF65EBEA-FA83-471A-9AA7-44DFDB09C15D","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q508464$86D5028E-564E-4F7B-B5AD-9A193B5FA4B4","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"4ecd2c89b0d0faccd561d2dcbe67344c34faeb28","datavalue":{"value":"W2282906890","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q508464$D2FA1EAE-22E9-45D8-A316-8842BCE0C1D5","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a9a83b1c36b5e98dbd113d29e71bf3946c06f7b1","datavalue":{"value":{"entity-type":"item","numeric-id":1431558,"id":"Q1431558"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f9a505e75077a167cdd45c0837cf9b29d2a6e662","datavalue":{"value":{"amount":"+0.7499062418937683","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q508464$BCEC0C28-146A-4F93-A48E-36B44BA3A617","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0a655efb7dfde9efdbb517335e35c0fba0504299","datavalue":{"value":{"entity-type":"item","numeric-id":997944,"id":"Q997944"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ba8bcca459bb0bfea17a9c2675484986ce5d0e1d","datavalue":{"value":{"amount":"+0.7337186336517334","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q508464$5471C9C6-F16B-48CF-AF2C-05CC7F1EAA4D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b4ad5206f004693d8a1abd327ca30f0e33f7a5e6","datavalue":{"value":{"entity-type":"item","numeric-id":2757412,"id":"Q2757412"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"800bef426d99396c7fe6498f1375dfa9e21ac50b","datavalue":{"value":{"amount":"+0.7071678042411804","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q508464$9838C281-2D81-4757-894D-7345CB56AE4C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"80306c9f8087d4768220faf08a37d9443eb376f9","datavalue":{"value":{"entity-type":"item","numeric-id":5418812,"id":"Q5418812"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"556a464fd28a50ac72ab2eb79aa35fc27eaeff21","datavalue":{"value":{"amount":"+0.7069190740585327","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q508464$FA56DC96-6475-4FFD-8908-32E883E57D17","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3be2ae75440d283e4527d730368f58facc5eedaa","datavalue":{"value":{"entity-type":"item","numeric-id":329827,"id":"Q329827"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"074491cabb59391d87224dbedcc1bd44e392714c","datavalue":{"value":{"amount":"+0.7059850692749023","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q508464$4154DD79-E184-4756-AA2B-CA4E5A3A4F33","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Mixing time of the fifteen puzzle","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Mixing_time_of_the_fifteen_puzzle"}}}}}