Algorithms, Complexity, and Entropy of the Bernard-Letac Fair-Sampling Construction
Abstract
Bernard and Letac (1971) introduced a method for uniform random sampling among m outcomes from an unknown biased source of independent and identically distributed symbols. The process terminates when the multinomial coefficient of the cumulative symbol counts equals zero modulo m. This study extends the computational and information-theoretic analysis of their construction by presenting five algorithms with formal correctness guarantees and comprehensive complexity analyses. For prime m=p, the Bernard-Letac framework is analyzed in greater detail. The Rényi entropies of the source yield an exact product formula for the expected number of draws. A first-order approximation consistently overestimates this value, and the entropy lower bound is never attained. As p, treated as a continuous parameter, approaches 1, the expected cost converges to a constant greater than 1, determined by the entire source distribution. Furthermore, for every prime modulus p and every finite alphabet I, an explicit automaton with p + |I| + 3 states computes the mod-p first-passage kernel of the walk from the base-p digits of its arguments, reducing the fair assignment cost from quadratic to nearly linear.
Related
- Decision-focused predictions via pessimistic bilevel optimization: complexity and algorithms
- Sparse Dictionary Learning for Measure-Valued Data via Linearized Optimal Transport: Efficient Algorithms and Sample Complexity
- Closure complexity of Bänsch-type algorithms for tetrahedral mesh refinement
- On skew-symmetric distributions and their use in Monte Carlo sampling algorithms: coordinate-free, Gibbs-style and manifold versions of the Barker proposal
- Minimizing the Arithmetic and Communication Complexity of Jacobi's Method for Eigenvalues and Singular Values: Part Two -- Parallel Algorithms
BibTeX
@misc{gravel2026algorithms,
title = {{Algorithms, Complexity, and Entropy of the Bernard-Letac Fair-Sampling Construction}},
author = {Claude Gravel},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2608.20234},
eprint = {2608.20234},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.20234},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Algorithms, Complexity, and Entropy of the Bernard-Letac Fair-Sampling Construction
AU - Claude Gravel
PY - 2026
DA - 2026/09/25
PB - arXiv
DO - 10.48550/arxiv.2608.20234
UR - https://arxiv.org/abs/2608.20234
AB - Bernard and Letac (1971) introduced a method for uniform random sampling among m outcomes from an unknown biased source of independent and identically distributed symbols. The process terminates when the multinomial coefficient of the cumulative symbol counts equals zero modulo m. This study extends the computational and information-theoretic analysis of their construction by presenting five algorithms with formal correctness guarantees and comprehensive complexity analyses. For prime m=p, the Bernard-Letac framework is analyzed in greater detail. The Rényi entropies of the source yield an exact product formula for the expected number of draws. A first-order approximation consistently overestimates this value, and the entropy lower bound is never attained. As p, treated as a continuous parameter, approaches 1, the expected cost converges to a constant greater than 1, determined by the entire source distribution. Furthermore, for every prime modulus p and every finite alphabet I, an explicit automaton with p + |I| + 3 states computes the mod-p first-passage kernel of the walk from the base-p digits of its arguments, reducing the fair assignment cost from quadratic to nearly linear.
ER -