Implementation of Glauber dynamics simulation of random lozenge tilings

2015/02/18

I’ve implemented the Glauber dynamics to (approximately) sample uniformly random lozenge tilings of polygons of Gelfand-Tsetlin type. These polygons are called sawtooth domains by J. Novak. This paper by B. Laslier and F.L. Toninelli establishes rate of convergence of the Glauber dynamics to the uniformly random lozenge tiling.

See here the many results of the simulations.

Classical references on uniformly random lozenge tilings include (the list below is by no means exhaustive)

• Cohn, H., Larsen, M. and Propp, J. (1998). The shape of a typical boxed plane partition. New York J. Math. 4 137–165

• Cohn, H., Kenyon, R. and Propp, J. (2001). A variational principle for domino tilings. J. Amer. Math. Soc. 14 297–346, link

• Kenyon, R. and Okounkov, A. (2007). Limit shapes and the complex Burgers equation. Acta Math. 199 263–302, arXiv:math-ph/0507007

I’ve also done some work on local and global asymptotics of uniformly random lozenge tilings [9], [10], [22].

Implementation

The simulation is performed in Python and is surprisingly simple because of the nice encoding of lozenge tilings of Gelfand-Tsetlin type polygons by interlacing integer arrays (the latter objects are also sometimes called Gelfand-Tsetlin schemes). This allows to sample interlacing arrays of depth up to 200-300 on my laptop in a reasonable time.

The drawing of tilings is performed in Mathematica, and it can be done in a static or a dynamic way. Here’s a relevant Mathematica code for static drawing (please remove backslashes in front of curly brackets before pasting):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
\[Lambda] = ReadList[fileName]
n := Length[\[Lambda][[1]]]
LozV[x_, y_, eps_] := \{EdgeForm[Thickness[eps]], Blue,
  Polygon[\{\{x - 1/2, y \}, \{x - 1/2, y + 1\}, \{x + 1/2, y \}, \{x + 1/2,
     y - 1\}, \{x - 1/2, y \}\}]\}
LozL[x_, y_, eps_] := \{EdgeForm[Thickness[eps]], Lighter[Yellow],
  Polygon[\{\{x - 1/2, y\}, \{x - 3/2, y + 1 \}, \{x - 1/2,
     y + 1\}, \{x + 1/2, y \}, \{x - 1/2, y \}\}]\}
LozS[x_, y_, eps_] := \{EdgeForm[Thickness[eps]], Lighter[Red],
  Polygon[\{\{x - 1/2, y\}, \{x - 1/2, y + 1\}, \{x + 1/2, y + 1\}, \{x + 1/2,
      y \}, \{x - 1/2, y \}\}]\}
FF[x_, k_] :=
 Sum[If[x >= \[Lambda][[1]][[k]][[i]] - i, 1, 0], \{i, 1, k\}] -
  If[k > 1,
   Sum[If[x >= \[Lambda][[1]][[k - 1]][[i]] - i, 1, 0], \{i, 1,
     k - 1\}], 0]
eps := 0.0004
t := \{\{1, 1/2\}, \{0, 1\}\}
Graphics[GeometricTransformation[\{Table[
    If[FF[x, k] == 1, LozS[x + 1, k - 1, eps],
     If[x + k > 0, LozL[x + 1, k - 1, eps]]], \{k, 1, n\}, \{x, -n + 1,
     n - 1\}],
   Table[LozV[\[Lambda][[1]][[i]][[j]] - j, i, eps], \{i, 1, n\}, \{j, 1,
      i\}]\}, t]]

The Python source code, as well as Mathematica files, are available at GitHub.

Remarks on sampling

• Coupling from the past could speed up the simulation, and produce an exact sampling

• For the hexagon, there are special shuffling algorithms to sample uniformly random (and even more generally distributed) lozenge tilings, see papers by Borodin, Gorin, and Rains (1, 2). See also a gallery here.