{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,3]],"date-time":"2026-10-03T19:05:44Z","timestamp":1791054344229,"version":"4.1.0"},"reference-count":19,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2001,1]]},"abstract":"<jats:p>Consider the following Markov chain, whose states are all domino tilings of a 2n\u00d7 2n chessboard: starting from some arbitrary tiling, pick a 2\u00d72 window uniformly at random. If the four squares appearing in this window are covered by two parallel dominoes, rotate the dominoes $90^{\\rm o}$ in place. Repeat many times. This process is used in practice to generate a random tiling and is a widely used tool in the study of the combinatorics of tilings and the behavior of dimer systems in statistical physics. Analogous Markov chains are used to randomly generate other structures on various two-dimensional lattices. This paper presents techniques which prove for the first time that, in many interesting cases, a small number of random moves suffice to obtain a uniform distribution.<\/jats:p>","DOI":"10.1137\/s0097539799360355","type":"journal-article","created":{"date-parts":[[2003,6,11]],"date-time":"2003-06-11T11:12:06Z","timestamp":1055329926000},"page":"167-192","source":"Crossref","is-referenced-by-count":97,"title":["Markov Chain Algorithms for Planar Lattice Structures"],"prefix":"10.1137","volume":"31","author":[{"given":"Michael","family":"Luby","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dana","family":"Randall","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Alistair","family":"Sinclair","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,27]]},"reference":[{"key":"R1","unstructured":"Khaled Al\u2010Khnaifes, Horst Sachs, Graphs, linear equations, determinants, and the number of perfect matchings, Bibliographisches Inst., Mannheim, 1990, 47\u20137192i:05193"},{"key":"R2","unstructured":"D. Aldous,\n                      Random walks on finite groups and rapidly mixing Markov chains\n                      , in S\u00e9minaire de Probabilit\u00e9s XVII, 1981\/82, Lecture Notes in Math. 986, Springer\u2010Verlag, Berlin, 1983, pp. 243\u2013297."},{"key":"R3","volume-title":"Exactly solved models in statistical mechanics","author":"Baxter Rodney","year":"1989"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(90)90057-4"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1214\/aoap\/1177005359"},{"key":"R6","volume-title":"Probability: theory and examples","author":"Durrett Richard","year":"1996"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1016\/0001-8708(85)90121-5"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1007\/BF01877590"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1137\/0218077"},{"key":"R10","unstructured":"W. Jockusch, J. Propp, and P. Shor,\n                      Random Domino Tilings and the Arctic Circle Theorem\n                      , preprint, 1995."},{"key":"R11","unstructured":"P. John and H. Sachs,\n                      Calculating the numbers of perfect matchings and of spanning trees, Pauling\u2019s orders, the characteristic polynomial, and the eigenvectors of a benzenoid system\n                      , in Topics in Current Chemistry, M. J. S. Dewar et al., eds., Advances in the Theory of Benzenoid Hydrocarbons 153, Springer\u2010Verlag, Berlin, 1990, pp. 145\u2013179."},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1007\/BF02183743"},{"key":"R13","unstructured":"Milena Mihail, Peter Winkler, On the number of Eulerian orientations of a graph, ACM, New York, 1992, 138\u201314593f:05059"},{"key":"R14","doi-asserted-by":"publisher","unstructured":"James Propp, David Wilson, Exact sampling with coupled Markov chains and applications to statistical mechanics, Proceedings of the Seventh International Conference on Random Structures and Algorithms (Atlanta, GA, 1995), Vol. 9, 1996, 223\u201325210.1002\/(SICI)1098-2418(199608\/09)9:1\/2<223:AID-RSA14>3.3.CO;2-R99k:60176","DOI":"10.1002\/(SICI)1098-2418(199608\/09)9:1\/2<223::AID-RSA14>3.3.CO;2-R"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1063\/1.533199"},{"key":"R16","unstructured":"A. Sinclair,\n                      Counting and Generating Combinatorial Structures: A Markov Chain Approach\n                      , Birkh\u00e4user, Boston, 1993."},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1080\/00029890.1990.11995660"},{"key":"R18","unstructured":"D. B. Wilson,\n                      Mixing Times of Lozenge Tiling and Card Shuffling Markov Chains\n                      , manuscript, 1997;"},{"key":"R18","unstructured":"also available online from http:\/\/research.microsoft.com\/\u223cdbwilson\/nlm."}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539799360355","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:20:24Z","timestamp":1787336424000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539799360355"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001,1]]},"references-count":19,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2001,1]]}},"alternative-id":["10.1137\/S0097539799360355"],"URL":"https:\/\/doi.org\/10.1137\/s0097539799360355","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2001,1]]}}}