Markov chain algorithms for planar lattice structures

Citation
M. Luby et al., Markov chain algorithms for planar lattice structures, SIAM J COMP, 31(1), 2001, pp. 167-192
Citations number
18
Language
INGLESE
art.tipo
Article
Categorie Soggetti
Computer Science & Engineering
Journal title
SIAM JOURNAL ON COMPUTING
ISSN journal
0097-5397 → ACNP
Volume
31
Issue
1
Year of publication
2001
Pages
167 - 192
Database
ISI
SICI code
0097-5397(20010729)31:1<167:MCAFPL>2.0.ZU;2-N
Abstract
Consider the following Markov chain, whose states are all domino tilings of a 2n x 2n chessboard: starting from some arbitrary tiling, pick a 2 x 2 wi ndow uniformly at random. If the four squares appearing in this window are covered by two parallel dominoes, rotate the dominoes 90 degrees in place. Repeat many times. This process is used in practice to generate a random ti ling 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-dimen sional lattices. This paper presents techniques which prove for the rst tim e that, in many interesting cases, a small number of random moves su ce to obtain a uniform distribution.