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 formula_1 be a combinatorial class with an ordinary generating function formula_2 which has a nonzero radius of convergence formula_3, i.e. is complex analytic. Formally speaking, if each object
formula_4 is equipped with a non-negative integer "size" formula_5, then the generating function formula_2 is defined as
formula_7
where formula_8 denotes the number of objects formula_4 of size formula_10. 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 formula_11 with a parameter formula_12 such that formula_13, denoted as
formula_14 returns an object formula_4 with probability
formula_16
Construction.
Finite sets.
If formula_17 is finite, then an element formula_18 is drawn with probability proportional to formula_19.
Disjoint union.
If the target class is a disjoint union of two other classes, formula_20, and the generating functions formula_21 and formula_22 of formula_23 and formula_24 are known, then the Boltzmann sampler for formula_1 can be obtained as
 formula_26
where formula_27 stands for "if the random variable formula_28 is 1, then execute formula_29, else execute formula_30". 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 formula_31 is a class constructed of ordered pairs formula_32 where formula_33 and formula_34, then the corresponding Boltzmann sampler formula_14 can be obtained as
formula_36
i.e. by forming a pair formula_32 with formula_38 and formula_39 drawn independently from formula_40 and formula_41.
Sequence.
If formula_11 is composed of all the finite sequences of elements of formula_23 with size of a sequence additively inherited from sizes of components, then the generating function of formula_11 is expressed as
formula_45, where formula_21 is the generating function of formula_23. Alternatively, the class formula_11 admits a recursive representation formula_49 This gives two possibilities for formula_14.
where formula_53 stands for "draw a random variable formula_28; if the value formula_55 is returned, then execute formula_29 independently formula_57 times and return the sequence obtained". Here, formula_58 stands for the geometric distribution formula_59.
Recursive classes.
As the first construction of the sequence operator suggests, Boltzmann samplers can be used recursively. If the target class formula_11 is a part of the system
 formula_61
where each of the expressions formula_62 involves only disjoint union, cartesian product and sequence operator, then the corresponding Boltzmann sampler is well defined. Given the argument value formula_12, 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 formula_11, exponential generating function is used instead:
formula_65
where formula_8 denotes the number of labelled objects formula_4 of size formula_10. 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 formula_11 is required to output an object formula_4 with probability
 formula_71
Labelled sets.
In the labelled universe, a class formula_11 can be composed of all the finite sets of elements of a class formula_23 with order-consistent relabellings. In this case, the exponential generating function of the class formula_11 is written as
formula_75
where formula_21 is the exponential generating function of the class formula_23. The Boltzmann sampler for formula_11 can be described as
 formula_79
where formula_80 stands for the standard Poisson distribution formula_81.
Labelled cycles.
In the cycle construction, a class formula_11 is composed of all the finite sequences of elements of a class formula_23, where two sequences are considered equivalent if they can be obtained by a cyclic shift. The exponential generating function of the class formula_11 is written as
formula_85
where formula_21 is the exponential generating function of the class formula_23. The Boltzmann sampler for formula_11 can be described as
 formula_89
where formula_90 describes the log-law distribution formula_91.
Properties.
Let formula_92 denote the random size of the generated object from formula_14. Then, the size has the first and the second moment satisfying
Examples.
Binary trees.
The class formula_24 of binary trees can be defined by the recursive specification
formula_98
and its generating function formula_22 satisfies an equation
formula_100 and can be evaluated as a solution of the quadratic equation
formula_101
The resulting Boltzmann sampler can be described recursively by
formula_102
Set partitions.
Consider various partitions of the set formula_103 into several non-empty classes, being disordered between themselves.
Using symbolic method, the class formula_11 of set partitions can be expressed as
formula_105
The corresponding generating function is equal to formula_106. Therefore, Boltzmann sampler can be described as
formula_107
where the positive Poisson distribution formula_108 is a Poisson distribution with a parameter formula_109 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 formula_11 be a labelled combinatorial class. The derivative operation is defined as follows: take a labelled object formula_4 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 formula_112 is the exponential generating function of the class formula_11, then the exponential generating function of the derivative class formula_114 is given byformula_115A differential specification is a recursive specification of type
 formula_116
where the expression formula_117 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 formula_4 is equipped with the composition size formula_119 which is a vector of non-negative integer numbers. Each of the size functions formula_120 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" formula_121 is then associated with a multi-parametric class, and is defined asformula_122A "Boltzmann sampler" for the multiparametric class formula_11 with a vector parameter formula_124 inside the domain of analyticity of formula_121, denoted as
formula_126 returns an object formula_4 with probability
formula_128
Multiparametric Boltzmann samplers have been constructed by Olivier Bodini and Yann Ponty. A polynomial-time algorithm for finding the numerical values of the parameters formula_129 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.
References.
 ;templatestyles src="Reflist/styles.css" / ;