A Bernard–Letac method for turning random draws into equally likely outcomes had the lowest reported mean cost among the listed methods in the paper’s displayed composite-modulus tests, involving non-prime target sizes. The analysis also states that the sampler halts almost surely and gives each of m possible outputs a probability of 1/m for every non-degenerate source distribution.
The guarantee is distribution-free: the output probabilities do not depend on π, the source distribution, even when the source is biased. The document is an arXiv version 1 preprint dated 20 Aug 2026.
From fairness to cost
The paper examines how many source draws and computational operations the construction needs. It covers expected complexity, information-theoretic efficiency and binary first-passage computation, and presents five algorithms with formal correctness guarantees and complexity analyses.
Prime moduli reveal the pattern
For a prime number of possible outputs, the paper reports an exact product formula for E(T), the expected number of source draws. It also finds that a first-order estimate, written as p/(1−U1(π)), always overstates the exact cost for a non-degenerate source and is never exact.
The exact cost depends on the full source distribution, not just on p. For prime p, E(T) is always greater than p, grows without bound as one source probability approaches 1, and satisfies E(T)/p→1 as p becomes large.
Entropy sets a floor
The analysis compares the sampler with an information limit. If H(π) denotes the source’s Shannon entropy, a measure of its uncertainty, every admissible exact uniform-sampling procedure must use at least log(m)/H(π) expected draws. The bound is strict for every m≥2 and every non-degenerate source, so the procedures considered do not attain it.
A limiting calculation shows why the entropy expression does not tell the whole story. When p is treated as a continuous parameter and approaches 1 from above, E(T) tends to a finite constant greater than 1. For a symmetric binary source, the reported value is 2.8457…, compared with 1/H(π)=1.4427….
The best point is in the middle
The efficiency measure η(p)=log p/[E(T)·H(π)] tends to zero as p approaches 1 from above and as p grows without bound, but reaches a maximum at an interior point. In the paper’s illustrative calculations, the maximum is about 0.44 near p=5 for π=(0.7,0.3), and about 0.46 near p=10 for π=(0.9,0.1).
The efficiency curve was unimodal in every computed case, meaning it showed one apparent peak, but the uniqueness of that peak remains unproved.
A seven-state binary shortcut
For the binary mod-2 case, the paper gives a seven-state finite automaton, or small state machine, to compute the first-passage kernel—the probabilities describing when a random path first reaches the stopping rule. It reports O(log T) word operations for the kernel and O(T log T) bit operations for exact fair assignment.
A promising but narrow comparison
The numerical comparison set the direct Bernard–Letac sampler against VN+Reject and VN+Lumbroso, measuring expected biased coin flips per uniform output. Each configuration used 2,000,000 samples.
Across the displayed composite-modulus configurations, Bernard–Letac had the lowest reported mean cost among the listed methods. Its mean divided by the Lumbroso value ranged from 0.40 to 0.73, with reported ratios of 0.73, 0.66, 0.45, 0.41, 0.40 and 0.41.
The comparison is limited to the configurations shown. No closed-form prediction for E(T) is known for composite moduli, so the table is empirical rather than a theorem verification; the paper reports no confidence intervals, and the Bernard–Letac values were empirical while the VN values were exact.
Paper data and sources
Original title: Algorithms, Complexity, and Entropy of the Bernard-Letac Fair-Sampling Construction
Authors: Claude Gravel
Journal/Repository: arXiv
Status: Preprint, not yet peer-reviewed
First online: 2026-08-20
DOI: Not available
Original paper · Full text