Boltzmann sampler explained

A Boltzmann sampler is an algorithm intended for random sampling of combinatorial structures. If the object size is viewed as its energy, and the argument of the corresponding generating function is interpreted in terms of the temperature of the physical system, then a Boltzmann sampler returns an object from a classical Boltzmann distribution.

The concept of Boltzmann sampler was proposed by Philippe Duchon, Philippe Flajolet, Guy Louchard and Gilles Schaeffer in 2004.^[1]

Description

The concept of Boltzmann sampling is closely related to the symbolic method in combinatorics.Let

l{C} be a combinatorial class with an ordinary generating function C(z) which has a nonzero radius of convergence \rho , i.e. is complex analytic. Formally speaking, if each objectc \in l C is equipped with a non-negative integer size \omega(c) , then the generating function C(z) is defined asC(z) = \sum _{c} z ^{\omega(c)} = \sum ^{inf ty} _{n =0} a _{n} z ^{n,}

where

a _{n} denotes the number of objects c \in l C of size n . The size function is typically used to denote the number of vertices in a tree or in a graph, the number of letters in a word, etc.

A Boltzmann sampler for the class

l C with a parameter z such that 0 < z < \rho , denoted as\Gamma l C(z) returns an object c \in l C with probabilityP(\Gamma l C(z) = c) = \dfrac{z ^{\omega(c)} }.

Construction

Finite sets

If

l{C} = \{ c _{1,} \ldots, c _{r} \} is finite, then an element c _{j} is drawn with probability proportional to z ^{\omega(c _{j)}} .

Disjoint union

If the target class is a disjoint union of two other classes,

l C = l A + l B , and the generating functions A(z) and B(z) of l A and l B are known, then the Boltzmann sampler for l{C} can be obtained as\left( \operatorname{Bern} \left( (A(z))/(C(z)) \right) \longrightarrow \Gamma l A(z) \mid \Gamma l B(z) \right)

where

(X \longrightarrow f \mid g) stands for "if the random variable X is 1, then execute f , else execute g ". More generally, if the disjoint union is taken over a finite set, the resulting Boltzmann sampler can be represented using a random choice with probabilities proportional to the values of the generating functions.

Cartesian product

If

l C = l A x l B is a class constructed of ordered pairs (a, b) where a \in l A and b \in l B , then the corresponding Boltzmann sampler \Gamma l C(z) can be obtained as\Gamma l C(z) = (\Gamma l A(z), \Gamma l B(z)),

i.e. by forming a pair

(a, b) with a and b drawn independently from \Gamma l A(z) and \Gamma l B(z) .

Sequence

If

l C is composed of all the finite sequences of elements of l A with size of a sequence additively inherited from sizes of components, then the generating function of l C is expressed asC(z) = \sum ^{inf ty} _{k =0} A(z) ^{k} = \dfrac{ 1 }{ 1 - A(z)} , where A(z) is the generating function of l A . Alternatively, the class l C admits a recursive representation l C = 1 + l A x l C. This gives two possibilities for \Gamma l C(z) .\Gamma l C(z) = \Gamma ( 1 + l A x l C)(z) = \left( \operatorname{Bern}\left( (1)/(C(z)) \right) \longrightarrow 1 | (\Gamma l A(z), \Gamma l C(z)) \right) \Gamma l C(z) = \left(\operatorname{Geom}(A(z)) \Longrightarrow \Gamma l C(z) \right)

where

(X \Longrightarrow f) stands for "draw a random variable X ; if the value X = x is returned, then execute f independently x times and return the sequence obtained". Here, \operatorname{Geom}(p) stands for the geometric distribution P(\operatorname{Geom}(p) = k) = p ^{k} ( 1 - p) .

Recursive classes

As the first construction of the sequence operator suggests, Boltzmann samplers can be used recursively. If the target class

l C is a part of the system\begin{cases} l C _{1} = \Phi _{1(lC} _{1,} \ldots, l C _{n,} l Z),\\ \vdots \\ l C _{n} = \Phi _{n(lC} _{1,} \ldots, l C _{n,} l Z), \end{cases}

where each of the expressions

\Phi _{k(lC} _{1,} \ldots, l C _{n,} l Z) involves only disjoint union, cartesian product and sequence operator, then the corresponding Boltzmann sampler is well defined. Given the argument value z , the numerical values of the generating functions can be obtained by Newton iteration.^[2]

Labelled structures

Boltzmann sampling can be applied to labelled structures. For a labelled combinatorial class

l C , exponential generating function is used instead:C(z) = \sum _{c} \dfrac{z ^{\omega(c)} } = \sum_^\infty a_n \dfrac,

where

a _{n} denotes the number of labelled objects c \in l C of size n . The operation of cartesian product and sequence need to be adjusted to take labelling into account, and the principle of construction remains the same.

In the labelled case, the Boltzmann sampler for a labelled class

l C is required to output an object c \in l C with probabilityP(\Gamma l C(z) = c) = (1)/(C(z)) (z ^{\omega(c)})/(\omega(c)!) .

Labelled sets

In the labelled universe, a class

l C can be composed of all the finite sets of elements of a class l A with order-consistent relabellings. In this case, the exponential generating function of the class l C is written asC(z) = \sum ^{inf ty} _{k =0} \dfrac{A(z) ^{k}{k!}} = e ^{A(z)}

where

A(z) is the exponential generating function of the class l A . The Boltzmann sampler for l C can be described as\Gamma l C(z) = \left(\operatorname{Poisson}(A(z)) \Longrightarrow \Gamma l C(z) \right)

where

\operatorname{Poisson}( λ ) stands for the standard Poisson distribution P(\operatorname{Poisson}(λ) = k) = e ^{-λ} \dfrac{ λ ^{k}{k!}} .

Labelled cycles

In the cycle construction, a class

l C is composed of all the finite sequences of elements of a class l A , where two sequences are considered equivalent if they can be obtained by a cyclic shift. The exponential generating function of the class l C is written asC(z) = \sum ^{inf ty} _{k =0} (A(z) ^{k})/(k) = log (1)/(1- A(z))

where

A(z) is the exponential generating function of the class l A . The Boltzmann sampler for l C can be described as\Gamma l C(z) = \left(\operatorname{Loga}(A(z)) \Longrightarrow \Gamma l C(z) \right)

where

\operatorname{Loga}( λ ) describes the log-law distribution P(\operatorname{Loga}(λ) = k) = \dfrac{ 1 }{ log ( 1 - λ ) ^{-1} } \dfrac.

Properties

Let

N denote the random size of the generated object from \Gamma l C(z) . Then, the size has the first and the second moment satisfyingE _{z} (N) = z \dfrac{C'(z)}{C(z)}; E _{z} (N ^{2)} = \dfrac{z ^{2} C''(z) + z C'(z)}{C(z)}; z \dfrac{d}{dz} E _{z} (N) = \operatorname{Var} _{z} (N) .

Examples

Binary trees

The class

l B of binary trees can be defined by the recursive specificationl B = l Z + l Z x l B x l B

and its generating function

B(z) satisfies an equationB(z) = z + z B(z) ^{2} and can be evaluated as a solution of the quadratic equationB(z) = \dfrac{ 1 - \sqrt{ 1 - 4 z ^{2}}{2z}}

The resulting Boltzmann sampler can be described recursively by

\Gamma l B(z) = \left( \operatorname{Bern}\left( (z)/(B(z)) \right) \longrightarrow l Z \mid \left( l Z, \Gamma l B(z), \Gamma l B(z) \right) \right)

Set partitions

Consider various partitions of the set

\{ 1 , 2 , \ldots, n\} into several non-empty classes, being disordered between themselves.Using symbolic method, the class l C of set partitions can be expressed asl C = \operatorname{Set}(\operatorname{Set} _{>0} ( l Z)).

The corresponding generating function is equal to

C(z) = e ^{e ^{z} -1} . Therefore, Boltzmann sampler can be described as\Gamma l C = \left( \operatorname{Poisson}(e ^{z} - 1 ) \Longrightarrow \left( \operatorname{Poisson} _{>0} (z) \Longrightarrow l Z \right) \right),

where the positive Poisson distribution

\operatorname{Poisson} _{>0} ( λ ) is a Poisson distribution with a parameter λ conditioned to take only positive values.

Further generalisations

The original Boltzmann samplers described by Philippe Duchon, Philippe Flajolet, Guy Louchard and Gilles Schaeffer only support basic unlabelled operations of disjoint union, cartesian product and sequence, and two additional operations for labelled classes, namely the set and the cycle construction. Since then, the scope of combinatorial classes for which a Boltzmann sampler can be constructed, has expanded.

Unlabelled structures

The admissible operations for unlabelled classes include such additional operations as Multiset, Cycle and Powerset. Boltzmann samplers for these operations have been described by Philippe Flajolet, Éric Fusy and Carine Pivoteau.^[3]

Differential specifications

Let

l C be a labelled combinatorial class. The derivative operation is defined as follows: take a labelled object c \in l C and replace an atom with the largest label with a distinguished atom without a label, therefore reducing a size of the resulting object by 1. If C(z) = \sum ^{inf ty} _{n =0} a _{n} \dfrac{z ^{n}{n!}} is the exponential generating function of the class l C , then the exponential generating function of the derivative class l C' is given by$$C\text{'}(z)\; =\; \backslash dfrac\; C(z)\; =\; \backslash sum\_^\backslash infty\; n\; a\_n\; \backslash frac$$A differential specification is a recursive specification of typel T' = \Phi( l T, l Z)

where the expression

\Phi( l T, l Z) involves only standard operations of union, product, sequence, cycle and set, and does not involve differentiation.

Boltzmann samplers for differential specifications have been constructed by Olivier Bodini, Olivier Roussel and Michèle Soria.^[4]

Multi-parametric Boltzmann samplers

A multi-parametric Boltzmann distribution for multiparametric combinatorial classes is defined similarly to the classical case. Assume that each object

c \in l C is equipped with the composition size \omega(c) = (\omega _{1(c),} \ldots, \omega _{d(c))} which is a vector of non-negative integer numbers. Each of the size functions \omega _{j(c)} can reflect one of the parameters of a data structure, such as the number of leaves of certain colour in a tree, the height of the tree, etc. The corresponding multivariate generating function C(z _{1,} \ldots, z _{d)} is then associated with a multi-parametric class, and is defined as$$C(z\_1,\; \backslash ldots,\; z\_d)\; =\; \backslash sum\_z\_1^\; \backslash cdots\; z\_d^.$$A Boltzmann sampler for the multiparametric class l C with a vector parameter \boldsymbol z = (z _{1,} \ldots, z _{d)} inside the domain of analyticity of C(z _{1,} \ldots, z _{d)} , denoted as\Gamma l C(z _{1,} \ldots, z _{d)} returns an object c \in l C with probabilityP( \Gamma l C(z _{1,} \ldots, z _{d)} = c) = (z ^{\omega _{1(c)}} _{1} … z ^{\omega _{d(c)}} _{d})/(C(z _{1,} \ldots, z _{d)}) .

Multiparametric Boltzmann samplers have been constructed by Olivier Bodini and Yann Ponty.^[5] A polynomial-time algorithm for finding the numerical values of the parameters

z _{1,} \ldots, z _{d} given the target parameter expectations, can be obtained by formulating an auxiliary convex optimisation problem

Applications

Boltzmann sampling can be used to generate algebraic data types for the sake of property-based testing.^[6]

Software

• Random Discrete Objects Suite (RDOS): http://lipn.fr/rdos/
• Combstruct package in Maple: https://www.maplesoft.com/support/help/Maple/view.aspx?path=combstruct
• Haskell package Boltzmann Brain: https://github.com/maciej-bendkowski/boltzmann-brain

Notes and References

1. Duchon. Philippe. Flajolet. Philippe. Louchard. Guy. Schaeffer. Gilles. July 2004. Boltzmann Samplers for the Random Generation of Combinatorial Structures. Combinatorics, Probability and Computing. en. 13. 4–5. 577–625. 10.1017/S0963548304006315. 1634696 . 0963-5483.
2. Pivoteau. Carine. Salvy. Bruno. Soria. Michèle. November 2012. Algorithms for combinatorial structures: Well-founded systems and Newton iterations. Journal of Combinatorial Theory, Series A. 119. 8. 1711–1773. 10.1016/j.jcta.2012.05.007. 0097-3165. free. 1109.2688.
3. Flajolet. Philippe. Fusy. Éric. Pivoteau. Carine. 2007-01-06. Boltzmann Sampling of Unlabelled Structures. 2007 Proceedings of the Fourth Workshop on Analytic Algorithmics and Combinatorics (ANALCO). 201–211. Philadelphia, PA. Society for Industrial and Applied Mathematics. 10.1137/1.9781611972979.5. 978-1-61197-297-9. free.
4. Bodini. Olivier. Roussel. Olivier. Soria. Michèle. December 2012. Boltzmann samplers for first-order differential specifications. Discrete Applied Mathematics. 160. 18. 2563–2572. 10.1016/j.dam.2012.05.022. 0166-218X. free.
5. Book: Bodini, Olivier Ponty, Yann. Multi-dimensional Boltzmann Sampling of Languages. 695180521.
6. Book: Lampropoulos . Leonidas . Gallois-Wong . Diane . Hriţcu . Cătălin . Hughes . John . Pierce . Benjamin C. . Xia . Li-yao . Proceedings of the 44th ACM SIGPLAN Symposium on Principles of Programming Languages . Beginner's luck: A language for property-based generators . 2017-01-01 . https://doi.org/10.1145/3009837.3009868 . POPL '17 . New York, NY, USA . Association for Computing Machinery . 114–129 . 10.1145/3009837.3009868 . 1607.05443 . 978-1-4503-4660-3. 14378582 .