Efficient sampling of the unlabeled structure of uniform random mappings and surjections
Abstract
This article deals with the sampling and statistics of uniform random mappings and surjections from [n]={1,…,n} to [k]={1,…,k}. More precisely, we focus on statistics that are invariant under relabeling of the domain and codomain. The structure of a mapping or surjection up to relabeling is captured by a compact representation called its profile. The profile records, for each occurring preimage size, the number of preimages of that size. We provide a complete set of algorithms that directly sample the profiles of uniform random mappings and surjections, covering the full parameter space. Their expected running times match the expected length of their outputs up to logarithmic factors. It is important to note that we make no assumption about the relationship between n and k; in particular, we do not assume that n/k is constant. All our guarantees are uniform in n and k. Achieving this uniformity substantially complicates the analysis. Our algorithms are based on exact-size Boltzmann samplers, which we accelerate by optimizing the cost of each sampling round and increasing the acceptance probability. As spin-off results, we answer, up to a logarithmic factor, an open question of Devroye and Los~25 on sampling profiles of random mappings when n>klog k, and obtain a sampler for uniform random surjections with expected running time O(nlog k), valid across the full parameter space.
Related
- Complex Analytic Structure of Hybrid Classes of Generalized Polynomial-like Mappings
- Climate-model factor separation with Shapley values and efficient sampling
- Deep operator learning for efficient sampling from invariant measures of stochastic differential equations
- Efficient Posterior Sampling for ℤ2 Synchronization
- Query-Efficient Rejection Sampling for Parallel Masked Diffusion
BibTeX
@misc{carayol2026efficient,
title = {{Efficient sampling of the unlabeled structure of uniform random mappings and surjections}},
author = {Arnaud Carayol and Pablo Rotondo},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2605.24068},
eprint = {2605.24068},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2605.24068},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Efficient sampling of the unlabeled structure of uniform random mappings and surjections
AU - Arnaud Carayol
AU - Pablo Rotondo
PY - 2026
DA - 2026/10/15
PB - arXiv
DO - 10.48550/arxiv.2605.24068
UR - https://arxiv.org/abs/2605.24068
AB - This article deals with the sampling and statistics of uniform random mappings and surjections from [n]={1,…,n} to [k]={1,…,k}. More precisely, we focus on statistics that are invariant under relabeling of the domain and codomain. The structure of a mapping or surjection up to relabeling is captured by a compact representation called its profile. The profile records, for each occurring preimage size, the number of preimages of that size. We provide a complete set of algorithms that directly sample the profiles of uniform random mappings and surjections, covering the full parameter space. Their expected running times match the expected length of their outputs up to logarithmic factors. It is important to note that we make no assumption about the relationship between n and k; in particular, we do not assume that n/k is constant. All our guarantees are uniform in n and k. Achieving this uniformity substantially complicates the analysis. Our algorithms are based on exact-size Boltzmann samplers, which we accelerate by optimizing the cost of each sampling round and increasing the acceptance probability. As spin-off results, we answer, up to a logarithmic factor, an open question of Devroye and Los~25 on sampling profiles of random mappings when n>klog k, and obtain a sampler for uniform random surjections with expected running time O(nlog k), valid across the full parameter space.
ER -