Boltzmann sampling of ordered structures
Uploaded by: Sergey Kirgizov
Upload date: 2021-02-22 20:22:04
Edited at: 2021-03-09 17:05:59
Edited by: Sergey Kirgizov


The article provides an extension of Boltzmann sampling to the realm of labeled combinatorial structures, enumerated by exponential generating functions and constructed using the box product. ---- [Boltzmann sampling]( is a general, pretty fast, technique for generate uniformely random combinatorial structures specified by structural equations. The key idea of Boltzmann sampling can be illustrated by the following example. Suppose you have a generating function $$f(x) = x + x^2 + x^2 + x^3 + x^3 + x^3 + x^3 + x^4 ...$$ corresponding to the one object of size one, two objects of size 2, four objects of size 3, etc. If you set, for example, $x = \frac{1}{2}$ then $$f\left(\frac{1}{2}\right) = \frac{1}{2} + \left(\frac{1}{2}\right)^2 + \left(\frac{1}{2}\right)^2 + \left(\frac{1}{2}\right)^3 + \left(\frac{1}{2}\right)^3 + \left(\frac{1}{2}\right)^3 + \left(\frac{1}{2}\right)^3 + \left(\frac{1}{2}\right)^4 ...$$ Now let's take $x$ such that $f(x) < \infty$, and chose an integer $k$. As you think, it quickly becomes clear that you can use this to chose a random object of size $k$. The probability equals precisely $\frac{x^k}{f(x)}$. For a given $k$ it is uniform. The elaboration of this idea in the context of structural equations (a.k.a. recursive decompositions, [symbolic method]( leads you to Boltzmann sampling technique. And knowing the values of generating functions together with corresponding recursive decompositions will allow you to generate a random object according to a uniform probability measure for any size. Shifting $x$ you will shift the mean size of a generating object. See [Boltzmann Samplers For The Random Generation Of Combinatorial Structures]( paper by Duchon, Flajolet, Louchard and Schaeffer for such elaboration.
Sergey Kirgizov at 2021-02-22 20:35:25
Edited by Sergey Kirgizov at 2021-03-09 15:27:15
See also these 2 related questions on MathOverflow:
Sergey Kirgizov at 2021-02-23 23:24:39
Edited by Sergey Kirgizov at 2021-02-23 23:24:45

Please consider to register or login to comment on the paper.