Authors

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.