Efficient Uniform Sampling of Surjections via their Profiles
Arnaud Carayol, Pablo Rotondo · 2026
Read Efficient Uniform Sampling of Surjections via their Profiles by Arnaud Carayol, Pablo Rotondo (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-2605-24068.txt.
Introduction
Carayol and Rotondo give methods for sampling profiles of uniform random maps and surjections, where only the shape matters, not the labels. A profile simply records, for each preimage size that occurs, how many preimages have that size. Their methods sample profiles directly across the whole parameter range, with no assumption linking n and k, and run near the output length up to log factors. Built on exact-size Boltzmann samplers, they also settle an open sampling question up to a log factor and yield a fast surjection sampler.
Catalog record
| CREATOR | Arnaud Carayol, Pablo Rotondo |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 96519 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.24068
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Efficient Uniform Sampling of Surjections via their Profiles Arnaud Carayol, Pablo Rotondo Abstract In this article, our aim is to develop efficient sampling algorithms for random surjections from [ n ] [n] to [ k ] [k] for all n ≥ k n\geq k . We make no assumption about the relationship between n n and k k . In particular, we do not make the common assumption that the ratio n k \frac{n}{k} is constant. All our guarantees are uniform in n n and k k . Our first insight is that all the complexity in sampling random surjections is captured by sampling a much smaller structure which we call the profile of the surjection. More precisely, the profile associates to each occurring preimage size s s the number of preimages of size s s . Using standard techniques, we show that the problem of sampling surjections reduces to sampling the profile with the induced distribution. This is partly explained by the fact that profiles are always sublinear, with at most 2 n \sqrt{2n} entries in the worst case. We provide a complete set of algorithms to directly sample the profile of a random surjection with the induced distribution, covering the full parameter space. These algorithms are shown to be optimal up to logarithmic factors in the expected size of the output. Our algorithms are based on exact-size Boltzmann samplers for the profiles, which are standard rejection-based samplers. We partition the parameter space into three main regions. In each region, we optimize both the rejection rate and the cost of each sampling round. Profiles capture a number of relevant statistics of random surjections and might be of independent interest. In a related context, profiles have been recently studied by Devroye et al. for random mappings. As a spin-off result, we answer an open question from [ 8 ] by providing an optimal algorithm also for the profiles of a random mapping when k > n / log n k>n/\log n . The results of this article are not only of theoretical interest but lead to samplers implementable in practice, allowing one to sample profiles for values of n n and k k way beyond the sizes of surjections that can fit in memory. Laboratoire d’Informatique Gaspard-Monge, Université Gustave Eiffel, [email protected] Laboratoire d’Informatique Gaspard-Monge, Université Gustave Eiffel, [email protected] ccs Theory of computation Generating random combinatorial structures keywords Random sampling, Boltzmann samplers, Surjections, Random Mappings † † runningtitle: Efficient Uniform Sampling of Surjections via their Profiles † † runningauthor: A. Carayol and P. Rotondo † † copyright: Arnaud Carayol and Pablo Rotondo 1 Introduction This work focuses on the problem of sampling a surjection uniformly at random from [n]=\{1,\ldots,n\} to [k]=\{1,\ldots,k\} for n\geq k\geq 2 without making any assumptions on the asymptotic relationship between n and k . Surjections from [n] to [k] are a fundamental object in combinatorics and arise both explicitly and as building blocks in many constructions. For instance, they encode words of length n over an alphabet of size k in which every letter appears at least once. Up to a permutation of [k] , surjections correspond to set partitions of [n] into k nonempty parts. More surprisingly, deterministic and complete finite-state automata in which all states are reachable from the initial state (accessible DFAs) can be efficiently sampled using random surjections (see [ 2 , 17 ] ). Indeed, such DFAs with n states over an alphabet of size \sigma are in bijection with a subset of surjections from [\sigma n+1] to [n] . Since this subset represents an asymptotically constant fraction of all such surjections, accessible DFAs can be sampled by a rejection sampler with an expected constant number of calls to the surjection sampler. 1.1 State of the art The number |\mathcal{S}(n,k)| of surjections from [n] to [k] is k!\genfrac{}{}{0.0pt}{}{n}{k} , where \genfrac{}{}{0.0pt}{}{n}{k} denotes the Stirling number of the second kind, which counts the number of set partitions of [n] into k parts. † † margin: This bound for the entropy is proven in Section B . The Shannon entropy of the uniform distribution on \mathcal{S}(n,k) is simply \log_{2}(|\mathcal{S}(n,k)|) , which is (n\log_{2}k)\times\left(1+O(\tfrac{\log\log n}{\log n})\right) , uniformly in n and k . As established in [ 16 ] , any uniform random sampler for \mathcal{S}(n,k) must, therefore, use this amount of fair random bits on average. In particular, in models where generating a fair random bit has constant cost, a sampling algorithm in O(n\log k) is optimal (up to the multiplicative constant). Exact-size Boltzmann samplers are the main general technique in the literature for uniform sampling of surjections. This technique is applicable for all n\geq k . These samplers are rejection-based: they generate candidate objects at each sampling round and repeat until the target size is obtained. Their complexity has been analyzed precisely under the assumption that k\sim\alpha n for some fixed \alpha\in(0,1) in [ 2 ] . In this regime, their expected complexity is O(n^{3/2}) as they perform O(\sqrt{n}) sampling rounds on average, each costing O(n) samples from simple distributions such as Geometric and Bernoulli. Still under this linearity assumption, Bassino and Sportiello [ 3 ] obtained a sampling algorithm with an expected complexity of O(n) samples from standard random variables 1 1 1 Here the notion of complexity does not count the number of fair random bits used but rather the number of sampling from standard random variables. As each of these sampling may require the production of a logarithmic number of fair random bits, there is no contradiction with the entropy lower bound. . Rather than generating a surjection directly, they reduce the problem to sampling a substructure, which they call the backbone of the surjection. They manage to lower the rejection rate of the associated Boltzmann sampler to make it constant. More precisely, the expected number of sampling rounds is constant but depends on the ratio \alpha=k/n . In particular, as \alpha tends to 0 , the constant is \sim\sqrt{\nicefrac{{2}}{{e}}\,\alpha}\exp(1/(2\alpha)) , which tends to infinity exponentially in \tfrac{1}{\alpha} (see the end of Section 4.1 in [ 3 ] ). In our experiments, this algorithm is not usable in practice to sample a surjection from [n] to [\frac{n}{20}] for n in the order of 10^{6} . 1.2 Our framework In this article we assume that operations on real numbers can be performed in O(1) with arbitrary precision. We include standard function like addition, exponential but also the special functions such as the log-gamma function, the regularized incomplete gamma function and the incomplete beta function. This kind of model is standard and referred to as an extended Real Arithmetic Model by some authors (e.g., [ 8 ] ). The inclusion of the special functions in our model is justified from a practical point of view by the existence of efficient approximation schemes [ 20 ] (see discussion in Section 4 ). Under such a model, sampling simple distributions such as Bernoulli, Poisson, Binomial can be done in O(1) expected time, see [ 9 ] . Unless stated otherwise all complexity expressed in this article are given in this model. The assumptions of the extended RAM model simplify the analysis at the cost of hiding an at most poly-logarithmic factor in