Achim Klenke

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.

Domino tiling
Domino
Lozenge tiling
Lozenge
Markov chain Markov chain
CFTP CFTP


Link

An overview over the recent development of the field of research can be found at the web site of David Wilson
ak, 07.11.2009