Boltzmann sampling

I'm reading Random sampling of plane partitions, by Olivier Bodini, Eric Fusy, and Carine Pivoteau. (arXiv:0712.0111v1). (Note: if you follow posts where I mention new things I've come across in the arXiv, you'll find that I'm currently reading papers I come across there at about a six-week lag.)

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ⁿ 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.