Generating random elements of finite distributive lattices. (English) Zbl 0885.05018

Electron. J. Comb. 4, No. 2, Research paper R15, 12 p. (1997); printed version J. Comb. 4, No. 2, 183-194 (1997).
Summary: This survey article describes a recent advance in the area of random generation, with applications to plane partitions, domino tilings, alternating sign matrices, and many other sorts of combinatorial objects. The algorithm is of the “random walk” or “Monte Carlo” variety, but unlike many such algorithms it does not have any initialization bias. The heart of the algorithm is the method of coupling from the past explored by David Wilson and myself in a joint article. For the sake of readability and motivation, I will start by focusing on the application of our method to plane partitions.


05A99 Enumerative combinatorics
05B99 Designs and configurations
Full Text: arXiv EuDML EMIS