Propp-Wilson Algorithm


In each of these applets, the regions are bipartite, meaning that each face may be colored black or white with no adjacent faces being the same color. Each tile covers one black face and one white face. In the case of the Aztec Diamond and hexagon, the symmetry of the faces forces each tile to be the same shape, a domino and a lozenge respectively. However, for the other regions, the layout is more complex, allowing two (Fortress) or more (Dungeon) types of tiles. In each case, the tiles are colored according to their phase (except in for the dungeon, where only tile shape is differentiated). These phases tend to form brickwork in the corners, but seem mostly random in the center. A large part of our research deals with determining where this brickwork ends (arctic boundary).

To form the tiling, each vertex is given an initial height value. Certain vertices will be surrounded by a "circle" of tiles, meaning that the tiles strictly go around the vertex matching black and white faces. In this case, the vertex may be raised or lowered, depending on whether the tiles cover black to white faces going clockwise or white to black. The height of the tiling is defined as the sum of these heights, normalized such that the minimum value is 0, and each raising move adjusts the height by 1. The Propp-Wilson Algorithm takes the unique tiling with the lowest possible height and the one with the highest and repeatedly performs these rotations to both until they are equivalent.

On the left of each applet is the minimum tiling, while the maximum tiling on the right. Once these tilings are formed, random raising and lowering moves will be performed on corresponding cycles in each tiling. Since the minimum tiling will have many more raising opportunities that lowering ones, its height, or total number of raising moves away from the minimum tiling, will rise quickly. This corresponds to high slope of the blue line in the graph. As it approaches the median height, however, these opportunities are far more balanced. In this case, the fact that the same moves are being applied to each tiling will help them converge. Similarly, this prevents the low tiling to pass the high tiling. However, when they converge, the tiling will not be completely random.

Before any rotations are carried out, a stopping point must be declared. In each of these applets, either 128 or 256 passes over each vertex will be executed initially. With luck, the tilings will converge before this time. If however, they do not, it must restart with the intention to do more passes, usually twice as many. When it gets to the final half of the passes however, rather than applying new random moves, the same moves as the first trial must be applied. As a result, the graphs of the heights from the new pass will always be squeezed withing the graphs from the first pass. Assuming that the tilings couple in this time, the tiling will be random upon completion of the passes. If not, it will try to accomplish the task in four times as many passes, etc. It is important to note that interrupting the process because it doesn't couple in any pass or doesn't look like it can will introduce bias over all random samples. Only by letting each proceed to the end, or performing special "blind" terminations can bias be avoided.