Boltzmann sampler

Random sampling algorithm

Not to be confused with Boltzmann machine.

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

[edit]

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

C ( z ) = ∑ c ∈ C z ω ( c ) = ∑ n = 0 ∞ a n z n , {\displaystyle C(z)=\sum _{c\in {\mathcal {C}}}z^{\omega (c)}=\sum _{n=0}^{\infty }a_{n}z^{n},}

where  a n {\displaystyle a_{n}} denotes the number of objects  c ∈ C {\displaystyle c\in {\mathcal {C}}} of size  n {\displaystyle 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  C {\displaystyle {\mathcal {C}}} with a parameter  z {\displaystyle z} such that  0 < z < ρ {\displaystyle 0<z<\rho } , denoted as  Γ C ( z ) {\displaystyle \Gamma {\mathcal {C}}(z)} returns an object  c ∈ C {\displaystyle c\in {\mathcal {C}}} with probability

P ( Γ C ( z ) = c ) = z ω ( c ) C ( z ) . {\displaystyle \mathbb {P} (\Gamma {\mathcal {C}}(z)=c)={\dfrac {z^{\omega (c)}}{C(z)}}.}

### Construction

[edit]

#### Finite sets

[edit]

If  C = { c 1 , … , c r } {\displaystyle {\mathcal {C}}=\\{c_{1},\ldots ,c_{r}\\}} is finite, then an element  c j {\displaystyle c_{j}} is drawn with probability proportional to  z ω ( c j ) {\displaystyle z^{\omega (c_{j})}} .

#### Disjoint union

[edit]

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

( Bern ⁡ ( A ( z ) C ( z ) ) ⟶ Γ A ( z ) ∣ Γ B ( z ) ) {\displaystyle \left(\operatorname {Bern} \left({\frac {A(z)}{C(z)}}\right)\longrightarrow \Gamma {\mathcal {A}}(z)\mid \Gamma {\mathcal {B}}(z)\right)}

where  ( X ⟶ f ∣ g ) {\displaystyle (X\longrightarrow f\mid g)} stands for "if the random variable  X {\displaystyle X} is 1, then execute  f {\displaystyle f} , else execute  g {\displaystyle 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

[edit]

If  C = A × B {\displaystyle {\mathcal {C}}={\mathcal {A}}\times {\mathcal {B}}} is a class constructed of ordered pairs  ( a , b ) {\displaystyle (a,b)} where  a ∈ A {\displaystyle a\in {\mathcal {A}}} and  b ∈ B {\displaystyle b\in {\mathcal {B}}} , then the corresponding Boltzmann sampler  Γ C ( z ) {\displaystyle \Gamma {\mathcal {C}}(z)} can be obtained as

Γ C ( z ) = ( Γ A ( z ) , Γ B ( z ) ) , {\displaystyle \Gamma {\mathcal {C}}(z)=(\Gamma {\mathcal {A}}(z),\Gamma {\mathcal {B}}(z)),}

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

#### Sequence

[edit]

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

1. Γ C ( z ) = Γ ( 1 + A × C ) ( z ) = ( Bern ⁡ ( 1 C ( z ) ) ⟶ 1 | ( Γ A ( z ) , Γ C ( z ) ) ) {\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)}
2. Γ C ( z ) = ( Geom ⁡ ( A ( z ) ) ⟹ Γ C ( z ) ) {\displaystyle \Gamma {\mathcal {C}}(z)=\left(\operatorname {Geom} (A(z))\Longrightarrow \Gamma {\mathcal {C}}(z)\right)}

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

#### Recursive classes

[edit]

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

{ C 1 = Φ 1 ( C 1 , … , C n , Z ) , ⋮ C n = Φ n ( C 1 , … , C n , Z ) , {\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}}}

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

#### Labelled structures

[edit]

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

C ( z ) = ∑ c ∈ C z ω ( c ) ω ( c ) ! = ∑ n = 0 ∞ a n z n n ! , {\displaystyle C(z)=\sum _{c\in {\mathcal {C}}}{\dfrac {z^{\omega (c)}}{\omega (c)!}}=\sum _{n=0}^{\infty }a_{n}{\dfrac {z^{n}}{n!}},}

where  a n {\displaystyle a_{n}} denotes the number of labelled objects  c ∈ C {\displaystyle c\in {\mathcal {C}}} of size  n {\displaystyle 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  C {\displaystyle {\mathcal {C}}} is required to output an object  c ∈ C {\displaystyle c\in {\mathcal {C}}} with probability

P ( Γ C ( z ) = c ) = 1 C ( z ) z ω ( c ) ω ( c ) ! . {\displaystyle \mathbb {P} (\Gamma {\mathcal {C}}(z)=c)={\frac {1}{C(z)}}{\frac {z^{\omega (c)}}{\omega (c)!}}.}

#### Labelled sets

[edit]

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

C ( z ) = ∑ k = 0 ∞ A ( z ) k k ! = e A ( z ) {\displaystyle C(z)=\sum _{k=0}^{\infty }{\dfrac {A(z)^{k}}{k!}}=e^{A(z)}}

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

Γ C ( z ) = ( Poisson ⁡ ( A ( z ) ) ⟹ Γ C ( z ) ) {\displaystyle \Gamma {\mathcal {C}}(z)=\left(\operatorname {Poisson} (A(z))\Longrightarrow \Gamma {\mathcal {C}}(z)\right)}

where  Poisson ⁡ ( λ ) {\displaystyle \operatorname {Poisson} (\lambda )} stands for the standard Poisson distribution P ( Poisson ⁡ ( λ ) = k ) = e − λ λ k k ! {\displaystyle \mathbb {P} (\operatorname {Poisson} (\lambda )=k)=e^{-\lambda }{\dfrac {\lambda ^{k}}{k!}}} .

#### Labelled cycles

[edit]

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

C ( z ) = ∑ k = 0 ∞ A ( z ) k k = log ⁡ 1 1 − A ( z ) {\displaystyle C(z)=\sum _{k=0}^{\infty }{\frac {A(z)^{k}}{k}}=\log {\frac {1}{1-A(z)}}}

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

Γ C ( z ) = ( Loga ⁡ ( A ( z ) ) ⟹ Γ C ( z ) ) {\displaystyle \Gamma {\mathcal {C}}(z)=\left(\operatorname {Loga} (A(z))\Longrightarrow \Gamma {\mathcal {C}}(z)\right)}

where  Loga ⁡ ( λ ) {\displaystyle \operatorname {Loga} (\lambda )} describes the log-law distribution P ( Loga ⁡ ( λ ) = k ) = 1 log ⁡ ( 1 − λ ) − 1 λ k k {\displaystyle \mathbb {P} (\operatorname {Loga} (\lambda )=k)={\dfrac {1}{\log(1-\lambda )^{-1}}}{\dfrac {\lambda ^{k}}{k}}} .

### Properties

[edit]

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

1. E z ( N ) = z C ′ ( z ) C ( z ) ; {\displaystyle \mathbb {E} _{z}(N)=z{\dfrac {C'(z)}{C(z)}};}
2. E z ( N 2 ) = z 2 C ″ ( z ) + z C ′ ( z ) C ( z ) ; {\displaystyle \mathbb {E} _{z}(N^{2})={\dfrac {z^{2}C''(z)+zC'(z)}{C(z)}};}
3. z d d z E z ( N ) = Var z ⁡ ( N ) {\displaystyle z{\dfrac {d}{dz}}\mathbb {E} _{z}(N)=\operatorname {Var} _{z}(N)} .

## Examples

[edit]

### Binary trees

[edit]

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

B = Z + Z × B × B {\displaystyle {\mathcal {B}}={\mathcal {Z}}+{\mathcal {Z}}\times {\mathcal {B}}\times {\mathcal {B}}}

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

B ( z ) = 1 − 1 − 4 z 2 2 z {\displaystyle B(z)={\dfrac {1-{\sqrt {1-4z^{2}}}}{2z}}}

The resulting Boltzmann sampler can be described recursively by

Γ B ( z ) = ( Bern ⁡ ( z B ( z ) ) ⟶ Z ∣ ( Z , Γ B ( z ) , Γ B ( z ) ) ) {\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)}

### Set partitions

[edit]

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

C = Set ⁡ ( Set > 0 ⁡ ( Z ) ) . {\displaystyle {\mathcal {C}}=\operatorname {Set} (\operatorname {Set} _{>0}({\mathcal {Z}})).}

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

Γ C = ( Poisson ⁡ ( e z − 1 ) ⟹ ( Poisson > 0 ⁡ ( z ) ⟹ Z ) ) , {\displaystyle \Gamma {\mathcal {C}}=\left(\operatorname {Poisson} (e^{z}-1)\Longrightarrow \left(\operatorname {Poisson} _{>0}(z)\Longrightarrow {\mathcal {Z}}\right)\right),}

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

## Further generalisations

[edit]

The original Boltzmann samplers described by Philippe Duchon, Philippe Flajolet, Guy Louchard and Gilles Schaeffer[1] 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

[edit]

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

[edit]

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

T ′ = Φ ( T , Z ) {\displaystyle {\mathcal {T}}'=\Phi ({\mathcal {T}},{\mathcal {Z}})}

where the expression  Φ ( T , Z ) {\displaystyle \Phi ({\mathcal {T}},{\mathcal {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

[edit]

A multi-parametric Boltzmann distribution for multiparametric combinatorial classes is defined similarly to the classical case. Assume that each object  c ∈ C {\displaystyle c\in {\mathcal {C}}} is equipped with the composition size  ω ( c ) = ( ω 1 ( c ) , … , ω d ( c ) ) {\displaystyle \omega (c)=(\omega _{1}(c),\ldots ,\omega _{d}(c))} which is a vector of non-negative integer numbers. Each of the size functions  ω j ( c ) {\displaystyle \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 , … , z d ) {\displaystyle C(z_{1},\ldots ,z_{d})} is then associated with a multi-parametric class, and is defined as C ( z 1 , … , z d ) = ∑ c ∈ C z 1 ω 1 ( c ) ⋯ z d ω d ( c ) . {\displaystyle C(z_{1},\ldots ,z_{d})=\sum _{c\in {\mathcal {C}}}z_{1}^{\omega _{1}(c)}\cdots z_{d}^{\omega _{d}(c)}.} A Boltzmann sampler for the multiparametric class  C {\displaystyle {\mathcal {C}}} with a vector parameter  z = ( z 1 , … , z d ) {\displaystyle {\boldsymbol {z}}=(z_{1},\ldots ,z_{d})} inside the domain of analyticity of  C ( z 1 , … , z d ) {\displaystyle C(z_{1},\ldots ,z_{d})} , denoted as

Γ C ( z 1 , … , z d ) {\displaystyle \Gamma {\mathcal {C}}(z_{1},\ldots ,z_{d})} returns an object  c ∈ C {\displaystyle c\in {\mathcal {C}}} with probability

P ( Γ C ( z 1 , … , z d ) = c ) = z 1 ω 1 ( c ) ⋯ z d ω d ( c ) C ( z 1 , … , z d ) . {\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})}}.}

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 , … , z d {\displaystyle z_{1},\ldots ,z_{d}} given the target parameter expectations, can be obtained by formulating an auxiliary convex optimisation problem[6]

## Applications

[edit]

This section needs expansion. You can help by adding to it. (February 2020)

|

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

## Software

[edit]

* 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

## References

[edit]

1. ^ a b Duchon, Philippe; Flajolet, Philippe; Louchard, Guy; Schaeffer, Gilles (July 2004). "Boltzmann Samplers for the Random Generation of Combinatorial Structures". Combinatorics, Probability and Computing. 13 (4–5): 577–625\. doi:10.1017/S0963548304006315 (inactive 29 December 2024). ISSN 0963-5483. S2CID 1634696.4–5&rft.pages=577-625&rft.date=2004-07&rft_id=https://api.semanticscholar.org/CorpusID:1634696#id-name=S2CID&rft.issn=0963-5483&rft_id=info:doi/10.1017/S0963548304006315&rft.aulast=Duchon&rft.aufirst=Philippe&rft.au=Flajolet,+Philippe&rft.au=Louchard,+Guy&rft.au=Schaeffer,+Gilles&rfr_id=info:sid/en.wikipedia.org:Boltzmann+sampler" class="Z3988">`{{cite journal}}`: CS1 maint: DOI inactive as of December 2024 (link)
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\. arXiv:1109.2688. doi:10.1016/j.jcta.2012.05.007. ISSN 0097-3165.
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). Philadelphia, PA: Society for Industrial and Applied Mathematics. pp. 201–211\. doi:10.1137/1.9781611972979.5. ISBN 978-1-61197-297-9.
4. ^ Bodini, Olivier; Roussel, Olivier; Soria, Michèle (December 2012). "Boltzmann samplers for first-order differential specifications". Discrete Applied Mathematics. 160 (18): 2563–2572\. doi:10.1016/j.dam.2012.05.022. ISSN 0166-218X.
5. ^ Bodini, Olivier Ponty, Yann. Multi-dimensional Boltzmann Sampling of Languages. OCLC 695180521.`{{cite book}}`: CS1 maint: multiple names: authors list (link)
6. ^ Bendkowski, Maciej; Bodini, Olivier; Dovgal, Sergey (January 2018). "Polynomial tuning of multiparametric combinatorial samplers". 2018 Proceedings of the Fifteenth Workshop on Analytic Algorithmics and Combinatorics (ANALCO). Society for Industrial and Applied Mathematics. pp. 92–106\. arXiv:1708.01212. doi:10.1137/1.9781611975062.9. ISBN 978-1-61197-506-2.
7. ^ Lampropoulos, Leonidas; Gallois-Wong, Diane; Hriţcu, Cătălin; Hughes, John; Pierce, Benjamin C.; Xia, Li-yao (2017-01-01). "Beginner's luck: A language for property-based generators". Proceedings of the 44th ACM SIGPLAN Symposium on Principles of Programming Languages. POPL '17. New York, NY, USA: Association for Computing Machinery. pp. 114–129\. arXiv:1607.05443. doi:10.1145/3009837.3009868. ISBN 978-1-4503-4660-3. S2CID 14378582.