Name
Abstract | ||
|---|---|---|
Consider the following Markov chain, whose states are all domino tilings of a 2n/spl times/2n chessboard: starting from some arbitrary tiling, pick a 2/spl times/2 window uniformly at random. If the four squares appearing in this window are covered by two parallel dominoes, rotate the dominoes in place. Repeat many times. This process is used in practice to generate a random tiling and is a key 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. The 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. |
Year | DOI | Venue |
|---|---|---|
2001 | 10.1137/S0097539799360355 | SIAM Journal on Computing |
Keywords | Field | DocType |
interesting case,random tiling,arbitrary tiling,markov chain algorithms,parallel domino,random move,following markov chain,rm o,planar lattice structure,spl time,analogous markov chain,key tool,dimer system,markov chain algorithm,planar lattice structures,domino tilings,combinatorics,random number generation,domino tiling,markov processes,solid modeling,physics,computer science,arctic,geometry,markov chain,testing,statistical physics,uniform distribution,lattices | Discrete mathematics,Combinatorics,Substitution tiling,Markov process,Lattice (order),Computer science,Markov chain,Uniform distribution (continuous),Domino,Planar,Random number generation | Journal |
Volume | Issue | ISSN |
31 | 1 | 0097-5397 |
ISBN | Citations | PageRank |
0-8186-7183-1 | 62 | 25.15 |
References | Authors | |
3 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Michael Luby | 1 | 9010 | 1319.35 |
| Dana Randall | 2 | 114 | 29.93 |
| alistair sinclair | 3 | 62 | 25.15 |