Boltzmann Sampling for Powersets without an Oracle

Jean C. Peyen · 2026

Read Boltzmann Sampling for Powersets without an Oracle by Jean C. Peyen (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-09508.txt.

Introduction

Jean C. Peyen shows how to sample powersets at random without a costly helper. The 2026 arXiv paper uses Boltzmann sampling, a method that draws random structures with known chances. For structures whose counting sequence stays bounded, the sampler runs efficiently without ever evaluating the generating function.

An algorithm is given, implemented, and tested. Its runtimes match those of existing Boltzmann samplers in the literature. The author also proposes two extensions for structures with unbounded counting sequences. Random sampling of this kind feeds testing, simulation, and the study of typical shapes in combinatorics.

Catalog record

CREATORJean C. Peyen
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE19 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2601-09508

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Boltzmann Sampling for Powersets without an Oracle Jean C. Peyen Abstract We show that powersets over structures with a bounded counting sequence can be sampled efficiently without evaluating the generating function. An algorithm is provided, implemented, and tested. Runtimes are comparable to existing Boltzmann samplers reported in the literature. In addition, we propose two examples of extensions for structures with an unbounded counting sequence. Keywords: powerset; occupancy problem; Boltzmann sampling; Poisson; thinning 1 Introduction The Boltzmann model is an efficient tool for the random generation of combinatorial objects introduced by Duchon et al. [ 1 ] . Define a combinatorial structure \mathcal{C} , endowed with a size function N:\mathcal{C}\rightarrow\mathbb{N}_{0} . The Boltzmann distribution over \mathcal{C} is given by \mathbb{P}(\gamma)=\frac{z^{N(\gamma)}}{C(z)}, (1) where C is the generating function of the structure \mathcal{C} . In order to control the size of the output, the parameter z has to be tuned for a given target, using the relation \mathbb{E}(N)=\frac{zC^{\prime}(z)}{C(z)}. (2) In many cases, the formalism of analytic combinatorics, introduced by Flajolet and Sedgewick [ 4 ] , systematises the implementation of samplers based on the Boltzmann model. Their implementation typically necessitates an oracle for the evaluation of the generating function. The oracle can be implemented with a fixed point iteration or with a Newton iteration [ 10 ] and is a source of numerical error. In this paper, we focus on sampling elements of structures of the form \mathcal{C}=\mathrm{PSet}(\mathcal{A}) , i.e. finite subsets of a structure \mathcal{A} . A Boltzmann sampler for powersets has already been proposed in [ 3 ] , it is based on prior sampling of a multiset and exclusion of elements with even multiplicities. This sampler requires an oracle for the generation of the multiset. Our aim is to develop an idea briefly mentioned in [ 9 ] . We show in Section 3 that powersets over structures with a bounded counting sequence can be sampled without using an oracle for the generating function. This method consists in recovering the Boltzmann distribution using an infinite occupancy model, with a random number of adequately distributed parts, and omitting the repetitions. It relies on the thinning method which can be applied because of the bound on the counting sequence. In Section 5 , we show that this approach is sufficiently robust to be extended to structures with unbounded counting sequence, assuming adequate conditions of growth. 2 Definitions and notations The occupancy problem consists in distributing a given number m of balls among a set of boxes with positive frequencies. The reader may refer to [ 2 ] for a presentation of the occupancy problem in its classical form or to [ 5 ] for the case with infinitely many boxes. Definition 1 . We denote by \mathcal{A} a combinatorial class endowed with a size function N:\mathcal{A}\rightarrow\mathbb{N}_{0} and by \mathcal{C} the structure \mathrm{PSet}(\mathcal{A}) , where the size function is defined by additivity. We define the level sets of the size function and the counting sequence \mathcal{A}_{n}=\{\ell\in\mathcal{A}~|~N(\ell)=n\},~~a_{n}=\sharp\mathcal{A}_{n}. (3) Definition 2 . We define \mathbb{P} as the distribution of the occupancy model with a random number of elements M . The elements are distributed over \mathcal{A} with frequency f=(f_{\ell})_{\ell\in\mathcal{A}} . We generically denote by \nu=(\nu_{\ell})_{\ell\in\mathcal{A}} the sequence of multiplicities of a configuration with distribution \mathbb{P} . This means that we have \nu_{\ell}=\sum_{k=1}^{M}\mathbf{1}_{\ell}(X_{k}), (4) where the X_{k} are i.i.d. with law \mathbb{P}(X_{k}=\ell)=f_{\ell}. (5) Definition 3 . We define \nu^{\prime} as the random element of \mathcal{C} obtained by setting to 1 the multiplicity of each element that has a non-zero multiplicity in \nu . In particular \mathbb{P}(\nu^{\prime}_{\ell}=1)=1-\mathbb{P}(\nu_{\ell}=0). (6) 3 Construction of the sampler To summarise the main idea: to generate an element of \mathrm{PSet}(\mathcal{A}) we first generate a configuration from an occupancy model with boxes labelled by the elements of \mathcal{A} and a random number of balls M . The distinction between the balls is omitted to obtain an element of \mathrm{MSet}(\mathcal{A}) . Finally, multiplicities are also omitted to obtain an element of \mathrm{PSet}(\mathcal{A}) . With an adequate choice of distribution for M and for the occupancy model, this process generates a configuration with the Boltzmann distribution as shown in Proposition 6 . The algorithm given in Proposition 7 can be used to implement this construction, as shown in Section 4 . Proposition 4 . \displaystyle\mathbb{P}(\nu^{\prime}_{\ell}=1) \displaystyle=1-G_{M}(1-f_{\ell}) (7) \displaystyle\mathrm{Cov}(\nu^{\prime}_{\ell},\nu^{\prime}_{\ell^{\prime}}) \displaystyle=G_{M}(1-(f_{\ell}+f_{\ell^{\prime}}))-G_{M}(1-f_{\ell})G_{M}(1-f_{\ell^{\prime}}) (8) where G_{M} is the probability generating function of M . Proof. Proof of ( 7 ) \displaystyle\mathbb{P}(\nu^{\prime}_{\ell}=1)=1-\mathbb{P}(\nu_{\ell}=0)=1-\sum_{m=0}^{\infty}\mathbb{P}(M=m)(1-f_{\ell})^{m}=1-G_{M}(1-f_{\ell}). Proof of ( 8 ) \displaystyle\mathrm{Cov}(\nu^{\prime}_{\ell},\nu^{\prime}_{\ell^{\prime}}) \displaystyle=\mathbb{P}(\nu^{\prime}_{\ell}\nu^{\prime}_{\ell^{\prime}}=1)-\mathbb{P}(\nu^{\prime}_{\ell}=1)\mathbb{P}(\nu^{\prime}_{\ell^{\prime}}=1) where \displaystyle\mathbb{P}(\nu^{\prime}_{\ell}\nu^{\prime}_{\ell^{\prime}}=1) \displaystyle=\mathbb{P}(\nu^{\prime}_{\ell}=1)+\mathbb{P}(\nu^{\prime}_{\ell^{\prime}}=1)-\mathbb{P}(\nu^{\prime}_{\ell}=1\text{ or }\nu^{\prime}_{\ell^{\prime}}=1) \displaystyle=\mathbb{P}(\nu^{\prime}_{\ell}=1)+\mathbb{P}(\nu^{\prime}_{\ell^{\prime}}=1)-\mathbb{P}((\nu_{\ell},\nu_{\ell})\neq(0,0)) \displaystyle=\left[1-G_{M}(1-f_{\ell})\right]+\left[1-G_{M}(1-f_{\ell^{\prime}})\right]-\left[1-G_{M}(1-(f_{\ell}+f_{\ell^{\prime}}))\right] \displaystyle=1-G_{M}(1-f_{\ell})-G_{M}(1-f_{\ell^{\prime}})+G_{M}(1-(f_{\ell}+f_{\ell^{\prime}})) and \displaystyle\mathbb{P}(\nu^{\prime}_{\ell}=1)\mathbb{P}(\nu^{\prime}_{\ell^{\prime}}=1) \displaystyle=1-G_{M}(1-f_{\ell})-G_{M}(1-f_{\ell^{\prime}})+G_{M}(1-f_{\ell})G_{M}(1-f_{\ell^{\prime}}). Thus we can conclude. ∎ Proposition 5 . 1. If M follows a Poisson distribution, then the \nu^{\prime}_{\ell} are mutually independent. 2. If the \nu^{\prime}_{\ell} are uncorrelated and the f_{\ell} accumulate at 0 (i.e. they take infinitely many non-zero values), then M follows a Poisson distribution. Proof. 1. Assume that M follows the Poisson distribution with parameter \lambda . Its probability generating function is G_{M}(t)=\exp{}(\lambda(t-1)) and \mathbb{P}(\nu^{\prime}_{\ell}=0)=\exp{}(-\lambda f_{\ell}) . Consider a subset E of \mathcal{A} . The probability that \nu^{\prime}_{\ell}=0 for all \ell\in E is \displaystyle\sum_{m=0}^{\infty}\mathbb{P}(M=m)\left(1-\sum_{\ell\in E}f_{\ell}\right)^{m}=G_{M}\left(1-\sum_{\ell\in E}f_{\ell}\right)=\exp{}\left(-\lambda\sum_{\ell\in E}f_{\ell}\right)=\prod_{\ell\in E}\exp(-\lambda f_{\ell}). We can conclude with a monotone class argument. 2. For all \ell,\ell^{\prime} , since \nu^{\prime}_{\ell} and \nu^{\prime}_{\ell^{\prime}} are uncorrelated, G_{M}(1-(f_{\ell}+f_{\ell^{\prime}}))-G_{M}(1-f_{\ell})\cdot G_{M}(1-f_{\ell^{\prime}})=0 in particular, if \ell=\ell^{\prime} , denoting g_{m}=\mathbb{P}(M=m) , we have \displaystyle G_{M}(1-2f_{\ell})=G_{M}(1-f_{\ell})^{2}\Leftrightarrow\sum_{m=0}^{\infty}g_{m}(1-2f_{\ell})^{m}=\sum_{m=0}^{\infty}(1-f_{\ell})^{m}\sum_{k=0}^{m}g_{k}g_{m-k} thus, as a consequence of the isolated zeros theorem (see [ 11 ] ) we have the functional equation G_{M}(1-2t)=G_{M}(1-t)^{2}, that identifies the generating function of a Poisson distribution. ∎ Proposition 6 . Let \mathcal{A} be a non-empty combinatorial structure with size function N:\mathcal{A}\rightarrow\mathbb{N}_{0} . Let f be the distribution f_{\ell}=\frac{\ln(1+z^{N(\ell)})}{\ln C(z)}~~,~~\ell\in\mathcal{A}, (9) where F is the generating function of \mathit{\mathrm{PSet}}(\mathcal{A}) , C(z)=\prod_{\ell\in\mathcal{A}}(1+z^{N(\ell)}). (10) Suppose that M follows the Poisson distribution with parameter \lambda=\ln(C) . The strict partition defined by the multiplicities \nu_{\ell}^{\prime} follows the Boltzmann distribution over \mathit{\mathrm{PSet}}(\mathcal{A}) . Proof. It is an immediate consequence of Proposition 4 which gives the marginal law of the \nu^{\prime}_{\ell} \mathbb{P}(\nu^{\prime}_{\ell}=1)=\frac{z^{N(\ell)}}{1+z^{N(\ell)}} and Proposition 5 which ensures the independence and allows to recover the Boltzmann distribution. ∎ We can avoid the explicit calculation of the parameter \lambda by using the Lewis thinning method; see [ 6 ] for a clear presentation of this method for Poisson processes, from which our case follows. Proposition 7 . Assume that the counting sequence of \mathcal{A} is bounded as follows a_{n}\leq\overline{a},~~\forall n\in\mathbb{N}_{0}. (11) Then, Algorithm 1 is a Boltzmann sampler for \mathcal{C} . Algorithm 1 Boltzmann (z) 1: Initialise \nu^{\prime}\leftarrow\emptyset 2: \overline{\lambda}\leftarrow{\frac{\overline{a}}{1-z}} 3: \overline{M}\leftarrow\text{Poiss}(\overline{\lambda}) 4: for i from 1 to \overline{M} do 5: n\leftarrow\text{Geom}(1-z) 6: if {\text{Bern}\left(\frac{a_{n}}{\overline{a}}\frac{\ln(1+z^{n})}{z^{n}}\right)} then 7: \ell\leftarrow\text{Unif}(\mathcal{A}_{n}) 8: \nu^{\prime}\leftarrow\nu^{\prime}\,\cup\,\{\ell\} 9: end if 10: end for Proof. We interpret the random variable M , defined in Proposition 6 , as the number of ticks per unit of time of a set of mutually independent exponential clocks with respective rate a_{n}\ln(1+z^{n}) . By thinning, each tick of these clocks is a tick of a faster clock with rate \overline{a}z^{n} which is accepted with probability \frac{a_{n}}{\overline{a}}\frac{\ln(1+z^{n})}{z_{n}}. For each tick of the set of faster clocks, the probability that it has been triggered by the n -th clock is \frac{\overline{a}z^{n}}{\sum_{k=0}^{\infty}\overline{a}z^{k}}=z^{n}(1-z). It matches the probability mass function of the geometric distribution sampled in the algorithm. Finally, we observe that elements of a level set \mathcal{A}_{n} have the

Read the complete text