朝花夕拾

轻飘飘的旧时光就这么溜走 转头回去看看时已匆匆数年

Domino shuffling algorithm on Aztec diamonds


Requirements:

  1. cairocffi and matplotlib for drawing random tilings.
  2. ImageMagick for making gif animations.

Usage

  1. To sample a random tiling of \({\rm AZ}(n)\), run

    python random_tiling.py -size imgsize -order n -prog matplotlib

    An example for imgsize=600 and n=60 is

  2. To make a gif animation of domino shuffling algorithm up to \(n\) rounds, run

    python domino_shuffling_animation.py -size imgsize -order n

    Below is an example for imgsize=400 and n=30:

What is domino shuffling algorithm

The following picture shows an Aztec diamond of order 10:

You can see from the top row to the bottom row there are \[2, 4, \ldots, 20, 20, \ldots, 4, 2\] unit squares piled up layers by layers.

In general an Aztec diamond of order \(n\) (denoted by \({\rm AZ}(n)\) for short) is obtained via this way by piling up \[2, 4, \ldots, 2n, 2n, \ldots, 4, 2\] unit squares.

Now we consider domino tilings of \({\rm AZ}(n)\), i.e. tilings with 1x2 dominoes. The following image shows one possible tiling of \({\rm AZ}(10)\):

Our first problem is:

Problem 1: How many domino tilings of \({\rm AZ}(n)\) are there?

This problem seems quite innocent at the first glance, but unfortunately all solutions known today (there are more than one dozen now) are not elementary, they either use quite sophisticated math or require genius insights.

The answer is \(2^{n(n+1)/2}\), a short and neat expression which suggests the problem itself should also have a neat and beautiful solution, and it does. This solution is called the domino shuffling algorithm we implemented in this project.

Before we state the algorithm, let's step further to another problem:

Problem 2: How to sample a random tiling of \({\rm AZ}(n)\) among all its \(2^{n(n+1)/2}\) different tilings from uniform probability?

Compare this with Wilson's uniform spanning tree algorithm and the coupling from the past algorithm in this repo, basically all of them are devised to do the same thing: sample a perfectly random element from a very very large set (in fact they can be generalized to sample under any given probability distribution). For \(n=100\), \({\rm AZ}(n)\) has \(2^{5050}\) different tilings, far more larger than the number of partices in the universe!

Domino Shuffling Algorithm

Think the plane as an infinite chessboard in which each cell is colored black or white and adjacent cells have different colorings.

A 2x2 block is called "black" if its topleft cell is colored black:

Place \({\rm AZ}(n)\) on this chessboard so that the leftmost cell in the top row is colored white:

The dominoes in the above figure are colored by four different colors according to their orientations which I'll explain later. I also added a background region of shape \({\rm AZ}(n+1)\).

Assume \(\mathcal{T}\) is a domino tiling of \({\rm AZ}(n)\), a 2x2 block is called "bad" if and only if it's black and it contains a pair of parellel dominoes in \(\mathcal{T}\).

The algorithm runs as follows:

  1. Deletion: find all bad blocks and remove all pairs of parallel dominoes in them:

  2. Sliding: for each domino that remains in \(\mathcal{T}\), move it one step according to its orientation. The orientation of a domino \(d\) s determined by the following rule: find the unique 2x2 black block \(B\) that contains \(d\), move \(d\) to the opposite position in \(B\): You can see the region that cotains all dominoes are now "enlarged" to \({\rm AZ}(n+1)\).

  3. Creation: it can be shown that after the moves the holes in \({\rm AZ}(n+1)\) can be filled up by disjoint 2x2 black blocks in a unique way (this assertion is the crux of the algorithm), use either a pair of horizontal or vertical dominoes to fill each block then one gets a domino tiling \(\mathcal{T}'\) of \({\rm AZ}(n+1)\): Further more, if \(\mathcal{T}\) is a random sample of tilings of \({\rm AZ}(n)\) from uniform probability, then \(\mathcal{T}'\) is also a random sample of tilings of \({\rm AZ}(n+1)\) from uniform probability.

So to sample a random tiling of \({\rm AZ}(n)\) from uniform probability, one can just start from a uniformly random tiling of \({\rm AZ}(1)\) (which is a 2x2 square, use a coin to choose one of its two tilings) and repeatly run the procedures deletion --> sliding --> creation --> deletion --> ... until one gets a tiling of \({\rm AZ}(n)\), then this tiling must be a perfectly random one.

The proof of this algorithm is quite non-trivial and one may refer to the two papers by Elkies, etc. and Propp for more details.