Monte Carlo sampling schemes are widely used in statistical
mechanics to study the properties of simple physical systems.
In this talk we examine methods for generating random
configurations. Consider the following Markov chain, whose
states are all domino tilings of a 2n by 2n chessboard:
starting from some arbitrary tiling, pick a 2 by 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,
such as lozenge tilings, Eulerian orientations (the ice
model) and three-colorings. We present techniques which
prove for the first time that, in many interesting cases,
a small number of random moves suffice to obtain a uniform
distribution.