🔢 mathematics

Algorithms, Complexity, and Entropy of the Bernard-Letac Fair-Sampling Construction

This paper extends the computational and information-theoretic analysis of the Bernard-Letac fair-sampling construction by presenting five formally verified algorithms, deriving exact and approximate formulas for expected sampling costs using Rényi entropies, and optimizing the binary case via a seven-state automaton to reduce complexity from quadratic to nearly linear.

Original authors: Claude Gravel

Published 2026-08-21

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Claude Gravel

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a world where every coin you flip is weighted, perhaps landing on heads more often than tails, or perhaps favoring one side so heavily that the other seems to almost never appear. For decades, mathematicians and computer scientists have asked a deceptively simple question: if you only have access to such a broken, biased source of randomness, can you still generate a perfectly fair outcome? Can you force a fair coin flip, or a fair choice among many options, using nothing but a stream of these flawed, unpredictable signals? The answer is yes, but the path to fairness is not straightforward. It requires a method that knows nothing about the bias, works for any kind of bias, and stops at just the right moment to ensure the result is truly random. This is the problem of fair sampling, a challenge that sits at the intersection of probability, number theory, and the very nature of information.

In a recent study, Claude Gravel, a researcher at Toronto Metropolitan University, has taken a deep dive into a specific solution to this problem, originally proposed in 1971 by Bernard and Letac. While the original work provided a clever mathematical recipe for fairness, it left many practical questions unanswered. Gravel's paper transforms that abstract recipe into a set of concrete, working algorithms, rigorously proving that they work and analyzing exactly how much effort they require. The study reveals that the cost of generating a fair result is not just a simple number but is deeply tied to the hidden structure of the biased source itself. By treating the problem through the lens of modern information theory, the research uncovers precise formulas for how long the process takes and shows that the most efficient way to use these biased signals depends on a specific type of mathematical "temperature" known as entropy.

The core of the Bernard–Letac method is a process of accumulation. Imagine a traveler walking through a grid, taking steps based on the symbols drawn from the biased source. If the source is a coin, the traveler moves right for heads and up for tails. The traveler keeps walking, recording the total number of steps in each direction, until they reach a specific stopping point. This stopping point is not chosen arbitrarily; it is a location where a complex counting rule, involving how many different ways the traveler could have arrived there, results in a number that is perfectly divisible by the number of outcomes you want to generate. For example, if you want a fair choice between five options, the process stops the moment the number of possible paths to the current location is a multiple of five. The magic of the method is that no matter how the coin is weighted, the paths leading to this stopping point can be divided into five groups of exactly equal size. This ensures that when the process stops, the final outcome is perfectly fair, even though the input was heavily biased.

Gravel's work begins by turning this elegant mathematical idea into five distinct, step-by-step computer algorithms. Each algorithm is designed to handle the task with formal guarantees of correctness. The study provides detailed instructions on how to compute the necessary counts efficiently, showing that the process can be carried out without needing to know the bias in advance. One of the most significant contributions is the analysis of how long this process takes. The researchers found that the average number of draws required to stop is not a fixed value but depends on the specific distribution of the biased source. They derived an exact formula for this average time, which involves an infinite product of terms related to the source's probabilities. This formula reveals that the cost is governed by a family of measures called Rényi entropies, which capture different aspects of the source's randomness.

A surprising finding in the paper is that a simple, intuitive guess for the cost of the process is always wrong. Many might assume that the cost is roughly determined by the most basic measure of randomness, known as Shannon entropy. However, the study proves that this simple approximation consistently overestimates the true cost. The actual cost is always lower than the simple guess, but the difference is not trivial. The researchers showed that as the number of desired outcomes grows very large, the cost does not shrink to the theoretical minimum predicted by basic information theory. Instead, it settles at a value that is strictly higher than the theoretical limit. This means that while the Bernard–Letac method is fair, it is not perfectly efficient; it inevitably wastes some of the randomness available in the source. The amount of waste depends on the entire distribution of the source, not just its overall entropy.

The paper also tackles the question of how to make the process faster on a computer. The original method requires a significant amount of calculation to determine which group a specific path belongs to, a step that can become very slow as the number of draws increases. For the specific case of generating a single fair bit (a choice between two options) from a binary source, Gravel discovered a way to bypass the heavy calculation entirely. By analyzing the structure of the paths, the researcher constructed a simple machine with just seven states that can determine the outcome by reading the binary digits of the path coordinates. This machine reduces the computational effort from a quadratic growth, which becomes unmanageable for large numbers, to a nearly linear growth, making the process vastly more practical for real-world applications.

The study further explores what happens when the number of outcomes is not a prime number but a composite one, such as six or ten. In these cases, the mathematical structure becomes much more irregular. The researchers found that for composite numbers, the process can get stuck in situations where certain stopping points are unreachable, and the groups of paths are not always of equal size. This irregularity prevents the researchers from finding a simple, closed-form formula for the cost in these cases, leaving it as an open question for future work. The paper suggests that for practical purposes, it might be better to round up to the nearest prime number to avoid these complications, though this has not been rigorously proven.

Ultimately, this research provides a comprehensive map of the terrain for fair sampling from biased sources. It confirms that the Bernard–Letac construction is a robust and correct method, but it also highlights its limitations and the precise mathematical reasons behind them. The work demonstrates that the cost of fairness is a complex quantity, shaped by the intricate details of the source's distribution. By providing exact formulas, efficient algorithms, and a clear understanding of the trade-offs involved, the study moves the field from abstract possibility to concrete implementation, offering a deeper understanding of how randomness can be extracted and purified from imperfect sources. The findings suggest that while we can achieve perfect fairness, the price we pay is a subtle and unavoidable inefficiency that is intrinsic to the nature of the biased source itself.

Technical Summary: Algorithms, Complexity, and Entropy of the Bernard–Letac Fair-Sampling Construction

Problem Statement
The paper addresses the fundamental problem of generating a uniform random outcome over $m$ possibilities from a biased, independent and identically distributed (i.i.d.) source with an unknown distribution $\pi$ over a finite or countable alphabet. The procedure must succeed for every admissible $\pi$ without prior knowledge of the bias, using a finite but random number of draws. This extends the classical von Neumann rejection scheme (1951) and the Hoeffding–Simons binary walk (1970) to arbitrary alphabets and arbitrary moduli $m$ .

Methodology
The study builds upon the 1971 construction by Bernard and Letac, which defines a stopping set $H_m = \{x \in \mathcal{M} : c(x) \equiv 0 \pmod m\}$ , where $c(x)$ is the multinomial coefficient of the cumulative symbol counts $x$ . The random walk terminates upon first reaching $H_m$ . The author extracts five distinct algorithms from the original combinatorial and number-theoretic theorems, providing formal correctness guarantees and complexity analyses.

Key methodological tools include:

Kummer's Theorem: Used to efficiently compute the $p$ -adic valuation of multinomial coefficients via carry propagation in base- $p$ addition.
Rényi Entropy: Utilized to characterize the expected stopping time, revealing that the complexity is governed by Rényi entropies of orders $p, p^2, p^3, \dots$ .
Finite Automata: A seven-state automaton is constructed to compute the mod-2 first-passage kernel of the binary walk, replacing a dynamic programming approach.
Transfer Theorems: Used to establish the finite nature of the section family of the kernel, enabling efficient computation.

Key Contributions and Results

Algorithmic Extraction and Complexity:
The paper formalizes five algorithms:
- Algorithm 1: Computes $v_p(c(x))$ in $O(|I| \cdot (\log_p(\max x_i) + \log_p |I|))$ time.
- Algorithm 2: The primary fair $m$ -way sampler. It halts almost surely and produces a uniform outcome. The path-assignment step (ranking the observed path) is identified as the computational bottleneck.
- Algorithm 3: A membership oracle for $H_{p^n}$ using a "Triangle Theorem" acceleration.
- Algorithm 4: A periodic lookup table for multinomial coefficients modulo $p^n$ .
- Algorithm 5: Computes the $p$ -adic limit $L(x) = \lim_{n \to \infty} c(p^n x)$ .
For the general case, the expected computational cost is $O(E(T) \cdot |I| \cdot \log T \cdot \omega(m))$ , where $\omega(m)$ is the number of distinct prime factors of $m$ .
Exact Expected Stopping Time and Entropy:
For a prime modulus $m=p$ , the paper derives an exact product formula for the expected number of draws $E(T)$ :
$E(T) = p \prod_{n=1}^{\infty} \frac{1 - (U_n(\pi))^p}{1 - U_n(\pi)}$
where $U_n(\pi) = \sum_i \pi_i^{p^n} = e^{(1-p^n)H_{p^n}(\pi)}$ .
- Approximation: A first-order approximation $E(T) \approx p / (1 - e^{(1-p)H_p(\pi)})$ is shown to always strictly overestimate the true value.
- Shannon Limit: As $p \to 1^+$ , $E(T)$ converges to a constant $C(\pi) > 1$ that depends on the full distribution $\pi$ , not just its Shannon entropy $H(\pi)$ . For a symmetric binary source, $C(\pi) \approx 2.8457$ , whereas the information-theoretic lower bound $1/H(\pi)$ is $\approx 1.4427$ .
- Efficiency: The efficiency $\eta(p) = \log p / (E(T)H(\pi))$ tends to 0 as $p \to 1^+$ and as $p \to \infty$ , attaining a maximum at an intermediate scale $p^*$ . The lower bound $E(T) \ge \log m / H(\pi)$ is never attained.
Binary Walk Optimization (Theorem D):
For the specific case of $m=2$ and a binary alphabet, the paper presents a transfer theorem. A seven-state automaton computes the parity of the number of monotone lattice paths avoiding the stopping set. This reduces the complexity of the fair group assignment from $O(T^2)$ (via dynamic programming) to $O(T \log T)$ bit operations.
Composite Moduli:
The paper notes that for composite $m$ , no closed-form expression for $E(T)$ exists due to the coupling of digit and carry structures across different prime bases. Numerical evidence suggests the Bernard–Letac method outperforms combinations of von Neumann debiasing and Lumbroso's Fast Dice Roller, even for composite moduli.

Significance and Claims
The paper claims to bridge the gap between the original combinatorial results of Bernard and Letac and modern computational and information-theoretic perspectives.

It provides the first exact product formula for the expected cost of the construction in terms of Rényi entropies.
It establishes that the efficiency of the sampler is strictly less than the information-theoretic lower bound and never attains it, contrasting with asymptotically optimal block procedures (like Elias) which trade off delay for efficiency.
It demonstrates that the Bernard–Letac construction, while prioritizing immediacy (online, sequential operation) over asymptotic optimality, offers a structural advantage by extracting useful information without an intermediate debiasing stage.
The reduction of the binary assignment cost to nearly linear time via the transfer automaton is presented as a significant computational improvement for the binary case.

Open Problems
The paper identifies several unresolved issues, including:

The existence of a closed-form $E(T)$ for composite moduli (P2).
Whether data-adaptive stopping boundaries can improve efficiency while maintaining fairness (P4).
The interpretation of the $p$ -adic limit $L(x)$ in terms of entropy (P5).
The existence of transfer systems for general prime moduli $p > 2$ (P1).

Technical Summary: Algorithms, Complexity, and Entropy of the Bernard–Letac Fair-Sampling Construction

More like this