The authors give a way to sample from plane partitions of size n uniformly at random. The method is not as efficient as one might like -- it begins by generating a plane partition of size

*approximately*n, where "approximately" means something like "within o(n) of", from a distribution which is uniform when restricted to partitions of exactly n, by a method known as "Boltzmann sampling", and then throws out those partitions which are not of size n. Still, a plane partition of size n can be chosen

*uniformly*at random in time O(n

^{4/3}). (Note that uniformity is important here; if we didn't care about the distribution, we could just write down a bunch of numbers that sum up to n and be done! More seriously, uniform sampling of this sort of combinatorial object with a bunch of highly interdependent parts tends to be tricky.)

But the idea I really like here is that of Boltzmann sampling, the inspiration for which I assume comes from physics. Namely, given a combinatorial class, we give each object a weight x

^{n}where

*n*is its size, where

*x*is a parameter between 0 than 1; then we pick objects with probabilities proportional to their weights. It turns out to be routine to give a Boltzmann sampler -- that is, an algorithm which picks a member of the class according to this distribution -- for any combinatorial class we can specify. (This is according to the papers of Duchon et al. and Flajolet et al. I've listed below, which I haven't actually read yet.) It reminds me of the partition function of statistical mechanics (the fact that this has "partition" in the name is a coincidence, as one could do this for any combinatorial class). Say a certain sort of physical system can occupy states labeled 1, 2, ..., N. Let E

_{j}be the energy of state

*j*. Then give each state the weight exp(-β E

_{j}), where β = 1/(kT) is the "inverse temperature"; the probabilities that the system occupies various states are proportional to these weights. Replacing energy by size and exp(-β) by x gives the combinatorial Boltzmann sampling. So the parameter

*x*is some sort of temperature.

**References**

Olivier Bodini, Eric Fusy, and Carine Pivoteau. Random sampling of plane partitions. arXiv:0712.0111v1.

P. Duchon, P. Flajolet, G. Louchard, and G. Schaeffer. Boltzmann samplers for the random generation of combinatorial structures.

*Combinatorics, Probability and Computing*, 13(4-5):577-625, 2004. Special issue on Analysis of Algorithms.

P. Flajolet, E. Fusy, and C. Pivoteau. Boltzmann sampling of unlabelled structures. In

*Proceedings of the 4th Workshop on Analytic Algorithms and Combinatorics, ANALCO'07 (New Orleans)*, pages 201-211. SIAM, 2007.

## No comments:

Post a Comment