Boltzmann sampler

Short description: Random sampling algorithm

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.

Description

The concept of Boltzmann sampling is closely related to the symbolic method in combinatorics. Let [math]\displaystyle{ \mathcal{C} }[/math] be a combinatorial class with an ordinary generating function [math]\displaystyle{ C(z) }[/math] which has a nonzero radius of convergence [math]\displaystyle{ \rho }[/math], i.e. is complex analytic. Formally speaking, if each object [math]\displaystyle{ c \in \mathcal C }[/math] is equipped with a non-negative integer size [math]\displaystyle{ \omega(c) }[/math], then the generating function [math]\displaystyle{ C(z) }[/math] is defined as

[math]\displaystyle{ C(z) = \sum_{c \in \mathcal C} z^{\omega(c)} = \sum_{n = 0}^\infty a_n z^n, }[/math]

where [math]\displaystyle{ a_n }[/math] denotes the number of objects [math]\displaystyle{ c \in \mathcal C }[/math] of size [math]\displaystyle{ n }[/math]. 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 [math]\displaystyle{ \mathcal C }[/math] with a parameter [math]\displaystyle{ z }[/math] such that [math]\displaystyle{ 0 \lt z \lt \rho }[/math], denoted as [math]\displaystyle{ \Gamma \mathcal C(z) }[/math] returns an object [math]\displaystyle{ c \in \mathcal C }[/math] with probability

[math]\displaystyle{ \mathbb P(\Gamma \mathcal C(z) = c) = \dfrac{z^{\omega(c)}}{C(z)}. }[/math]

Construction

Finite sets

If [math]\displaystyle{ \mathcal{C} = \{ c_1, \ldots, c_r \} }[/math] is finite, then an element [math]\displaystyle{ c_j }[/math] is drawn with probability proportional to [math]\displaystyle{ z^{\omega(c_j)} }[/math].

Disjoint union

If the target class is a disjoint union of two other classes, [math]\displaystyle{ \mathcal C = \mathcal A + \mathcal B }[/math], and the generating functions [math]\displaystyle{ A(z) }[/math] and [math]\displaystyle{ B(z) }[/math] of [math]\displaystyle{ \mathcal A }[/math] and [math]\displaystyle{ \mathcal B }[/math] are known, then the Boltzmann sampler for [math]\displaystyle{ \mathcal{C} }[/math] can be obtained as

[math]\displaystyle{ \left( \operatorname{Bern} \left( \frac{A(z)}{C(z)} \right) \longrightarrow \Gamma \mathcal A(z) \mid \Gamma \mathcal B(z) \right) }[/math]

where [math]\displaystyle{ (X \longrightarrow f \mid g) }[/math] stands for "if the random variable [math]\displaystyle{ X }[/math] is 1, then execute [math]\displaystyle{ f }[/math], else execute [math]\displaystyle{ g }[/math]". 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 [math]\displaystyle{ \mathcal C = \mathcal A \times \mathcal B }[/math] is a class constructed of ordered pairs [math]\displaystyle{ (a, b) }[/math] where [math]\displaystyle{ a \in \mathcal A }[/math] and [math]\displaystyle{ b \in \mathcal B }[/math], then the corresponding Boltzmann sampler [math]\displaystyle{ \Gamma \mathcal C(z) }[/math] can be obtained as

[math]\displaystyle{ \Gamma \mathcal C(z) = (\Gamma \mathcal A(z), \Gamma \mathcal B(z)), }[/math]

i.e. by forming a pair [math]\displaystyle{ (a, b) }[/math] with [math]\displaystyle{ a }[/math] and [math]\displaystyle{ b }[/math] drawn independently from [math]\displaystyle{ \Gamma \mathcal A(z) }[/math] and [math]\displaystyle{ \Gamma \mathcal B(z) }[/math].

Sequence

If [math]\displaystyle{ \mathcal C }[/math] is composed of all the finite sequences of elements of [math]\displaystyle{ \mathcal A }[/math] with size of a sequence additively inherited from sizes of components, then the generating function of [math]\displaystyle{ \mathcal C }[/math] is expressed as [math]\displaystyle{ C(z) = \sum_{k=0}^\infty A(z)^k = \dfrac{1}{1 - A(z)} }[/math], where [math]\displaystyle{ A(z) }[/math] is the generating function of [math]\displaystyle{ \mathcal A }[/math]. Alternatively, the class [math]\displaystyle{ \mathcal C }[/math] admits a recursive representation [math]\displaystyle{ \mathcal C = 1 + \mathcal A \times \mathcal C. }[/math] This gives two possibilities for [math]\displaystyle{ \Gamma \mathcal C(z) }[/math].

1. [math]\displaystyle{ \Gamma \mathcal C(z) = \Gamma (1 + \mathcal A \times \mathcal C)(z) =\left( \operatorname{Bern}\left(\frac{1}{C(z)}\right) \longrightarrow 1 \, \Big|\, (\Gamma \mathcal A(z), \Gamma \mathcal C(z)) \right) }[/math]
2. [math]\displaystyle{ \Gamma \mathcal C(z) = \left( \operatorname{Geom}(A(z)) \Longrightarrow \Gamma \mathcal C(z) \right) }[/math]

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

Recursive classes

As the first construction of the sequence operator suggests, Boltzmann samplers can be used recursively. If the target class [math]\displaystyle{ \mathcal C }[/math] is a part of the system

[math]\displaystyle{ \begin{cases} \mathcal C_1 = \Phi_1(\mathcal C_1, \ldots, \mathcal C_n, \mathcal Z),\\ \qquad \vdots \\ \mathcal C_n = \Phi_n(\mathcal C_1, \ldots, \mathcal C_n, \mathcal Z), \end{cases} }[/math]

where each of the expressions [math]\displaystyle{ \Phi_k(\mathcal C_1, \ldots, \mathcal C_n, \mathcal Z) }[/math] involves only disjoint union, cartesian product and sequence operator, then the corresponding Boltzmann sampler is well defined. Given the argument value [math]\displaystyle{ z }[/math], the numerical values of the generating functions can be obtained by Newton iteration.

Labelled structures

Boltzmann sampling can be applied to labelled structures. For a labelled combinatorial class [math]\displaystyle{ \mathcal C }[/math], exponential generating function is used instead:

[math]\displaystyle{ C(z) = \sum_{c \in \mathcal C} \dfrac{z^{\omega(c)}}{\omega(c)!} = \sum_{n = 0}^\infty a_n \dfrac{z^n}{n!}, }[/math]

where [math]\displaystyle{ a_n }[/math] denotes the number of labelled objects [math]\displaystyle{ c \in \mathcal C }[/math] of size [math]\displaystyle{ n }[/math]. 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 [math]\displaystyle{ \mathcal C }[/math] is required to output an object [math]\displaystyle{ c \in \mathcal C }[/math] with probability

[math]\displaystyle{ \mathbb P(\Gamma \mathcal C(z) = c) = \frac{1}{C(z)} \frac{z^{\omega(c)}}{\omega(c)!}. }[/math]

Labelled sets

In the labelled universe, a class [math]\displaystyle{ \mathcal C }[/math] can be composed of all the finite sets of elements of a class [math]\displaystyle{ \mathcal A }[/math] with order-consistent relabellings. In this case, the exponential generating function of the class [math]\displaystyle{ \mathcal C }[/math] is written as

[math]\displaystyle{ C(z) = \sum_{k = 0}^\infty \dfrac{A(z)^k}{k!} = e^{A(z)} }[/math]

where [math]\displaystyle{ A(z) }[/math] is the exponential generating function of the class [math]\displaystyle{ \mathcal A }[/math]. The Boltzmann sampler for [math]\displaystyle{ \mathcal C }[/math] can be described as

[math]\displaystyle{ \Gamma \mathcal C(z) = \left( \operatorname{Poisson}(A(z)) \Longrightarrow \Gamma \mathcal C(z) \right) }[/math]

where [math]\displaystyle{ \operatorname{Poisson}(\lambda) }[/math] stands for the standard Poisson distribution [math]\displaystyle{ \mathbb P(\operatorname{Poisson}(\lambda) = k) = e^{-\lambda} \dfrac{\lambda^k}{k!} }[/math].

Labelled cycles

In the cycle construction, a class [math]\displaystyle{ \mathcal C }[/math] is composed of all the finite sequences of elements of a class [math]\displaystyle{ \mathcal A }[/math], where two sequences are considered equivalent if they can be obtained by a cyclic shift. The exponential generating function of the class [math]\displaystyle{ \mathcal C }[/math] is written as

[math]\displaystyle{ C(z) = \sum_{k = 0}^\infty \frac{A(z)^k}{k} = \log \frac{1}{1 - A(z)} }[/math]

where [math]\displaystyle{ A(z) }[/math] is the exponential generating function of the class [math]\displaystyle{ \mathcal A }[/math]. The Boltzmann sampler for [math]\displaystyle{ \mathcal C }[/math] can be described as

[math]\displaystyle{ \Gamma \mathcal C(z) = \left( \operatorname{Loga}(A(z)) \Longrightarrow \Gamma \mathcal C(z) \right) }[/math]

where [math]\displaystyle{ \operatorname{Loga}(\lambda) }[/math] describes the log-law distribution [math]\displaystyle{ \mathbb P(\operatorname{Loga}(\lambda) = k) = \dfrac{1}{\log(1 - \lambda)^{-1}} \dfrac{\lambda^k}{k} }[/math].

Properties

Let [math]\displaystyle{ N }[/math] denote the random size of the generated object from [math]\displaystyle{ \Gamma \mathcal C(z) }[/math]. Then, the size has the first and the second moment satisfying

1. [math]\displaystyle{ \mathbb E_z (N) = z \dfrac{C'(z)}{C(z)}; }[/math]
2. [math]\displaystyle{ \mathbb E_z (N^2) = \dfrac{z^2 C''(z) + z C'(z)}{C(z)}; }[/math]
3. [math]\displaystyle{ z \dfrac{d}{dz} \mathbb E_z (N) = \operatorname{Var}_z (N) }[/math].

Examples

Binary trees

The class [math]\displaystyle{ \mathcal B }[/math] of binary trees can be defined by the recursive specification

[math]\displaystyle{ \mathcal B = \mathcal Z + \mathcal Z \times \mathcal B \times \mathcal B }[/math]

and its generating function [math]\displaystyle{ B(z) }[/math] satisfies an equation [math]\displaystyle{ B(z) = z + z B(z)^2 }[/math] and can be evaluated as a solution of the quadratic equation

[math]\displaystyle{ B(z) = \dfrac{1 - \sqrt{1 - 4 z^2}}{2z} }[/math]

The resulting Boltzmann sampler can be described recursively by

[math]\displaystyle{ \Gamma \mathcal B(z) = \left( \operatorname{Bern}\left( \frac{z}{B(z)} \right) \longrightarrow \mathcal Z \mid \left( \mathcal Z, \, \Gamma \mathcal B(z), \, \Gamma \mathcal B(z) \right) \right) }[/math]

Set partitions

Consider various partitions of the set [math]\displaystyle{ \{1, 2, \ldots, n\} }[/math] into several non-empty classes, being disordered between themselves. Using symbolic method, the class [math]\displaystyle{ \mathcal C }[/math] of set partitions can be expressed as

[math]\displaystyle{ \mathcal C = \operatorname{Set}(\operatorname{Set}_{\gt 0}(\mathcal Z)). }[/math]

The corresponding generating function is equal to [math]\displaystyle{ C(z) = e^{e^z - 1} }[/math]. Therefore, Boltzmann sampler can be described as

[math]\displaystyle{ \Gamma \mathcal C = \left( \operatorname{Poisson}(e^z - 1) \Longrightarrow \left( \operatorname{Poisson}_{\gt 0} (z) \Longrightarrow \mathcal Z \right) \right), }[/math]

where the positive Poisson distribution [math]\displaystyle{ \operatorname{Poisson}_{\gt 0}(\lambda) }[/math] is a Poisson distribution with a parameter [math]\displaystyle{ \lambda }[/math] 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.

Differential specifications

Let [math]\displaystyle{ \mathcal C }[/math] be a labelled combinatorial class. The derivative operation is defined as follows: take a labelled object [math]\displaystyle{ c \in \mathcal C }[/math] 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 [math]\displaystyle{ C(z) = \sum_{n=0}^\infty a_n \dfrac{z^n}{n!} }[/math] is the exponential generating function of the class [math]\displaystyle{ \mathcal C }[/math], then the exponential generating function of the derivative class [math]\displaystyle{ \mathcal C' }[/math]is given by[math]\displaystyle{ C'(z) = \dfrac{d}{dz} C(z) = \sum_{n = 0}^\infty n a_n \frac{z^{n-1}}{n!} }[/math]A differential specification is a recursive specification of type

[math]\displaystyle{ \mathcal T' = \Phi(\mathcal T, \mathcal Z) }[/math]

where the expression [math]\displaystyle{ \Phi(\mathcal T, \mathcal Z) }[/math] 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.

Multi-parametric Boltzmann samplers

A multi-parametric Boltzmann distribution for multiparametric combinatorial classes is defined similarly to the classical case. Assume that each object [math]\displaystyle{ c \in \mathcal C }[/math] is equipped with the composition size [math]\displaystyle{ \omega(c) = (\omega_1(c), \ldots, \omega_d(c)) }[/math] which is a vector of non-negative integer numbers. Each of the size functions [math]\displaystyle{ \omega_j(c) }[/math] 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 [math]\displaystyle{ C(z_1, \ldots, z_d) }[/math] is then associated with a multi-parametric class, and is defined as[math]\displaystyle{ C(z_1, \ldots, z_d) = \sum_{c \in \mathcal C} z_1^{\omega_1(c)} \cdots z_d^{\omega_d(c)}. }[/math]A Boltzmann sampler for the multiparametric class [math]\displaystyle{ \mathcal C }[/math] with a vector parameter [math]\displaystyle{ \boldsymbol z = (z_1, \ldots, z_d) }[/math] inside the domain of analyticity of [math]\displaystyle{ C(z_1, \ldots, z_d) }[/math], denoted as

[math]\displaystyle{ \Gamma \mathcal C(z_1, \ldots, z_d) }[/math] returns an object [math]\displaystyle{ c \in \mathcal C }[/math] with probability

[math]\displaystyle{ \mathbb P( \Gamma \mathcal C(z_1, \ldots, z_d) = c) = \frac{z_1^{\omega_1(c)} \cdots z_d^{\omega_d(c)}}{C(z_1, \ldots, z_d)}. }[/math]

Multiparametric Boltzmann samplers have been constructed by Olivier Bodini and Yann Ponty. A polynomial-time algorithm for finding the numerical values of the parameters [math]\displaystyle{ z_1, \ldots, z_d }[/math] 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.

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