Computer simulation of random tilings: domino and lozenge.
Markov chain method
The aim is to choose among all possible tilings of a square with domino blocks, say, one
tiling at random (according to the uniform distribution). The Markov chain method is based
on applying random changes to a given configuration very often. Since the distribution
of the chain converges to the uniform distribution, running the chain suffiently
long should give a uniformly distributed random tiling. One major problem is that
it is usually unknown what sufficiently long is exactly. The other problem
is that you will always end up with a sample that is only approximately uniformly distributed.
Coupling from the past
James Propp and David Wilson proposed the method of coupling from the past (a variation
of this method is due to Jim Fill). Here step by step you generate a chain that
starts further and further back in the past and at each time uses the
same random changes.
The method works effectively if the tilings can be ordered
(partially) and if the random changes respect the ordering. For lozenge tilings
you virtually see a height profile that induces a partial ordering. For domino
tilings, there is a coding of the tilings as east-west paths that induces the
partial order.
Once that the maximal and the minimal tiling end up in the same state the simulation
stops and yields a perfect sample of a uniformly random tiling. The simulations show
the fate of the minimal and the maximal configuration. For the domino tiling
also the paths are illustrated.
Java Applets
For her diplom thesis in Mainz, Kerstin Roll (2007) programmed simulations as
java applets that can be viewed here.
