A Practical Implementation of the Bernoulli Factory
Abstract
The Bernoulli Factory is an algorithm that transforms a series of i.i.d. Bernoulli random variables with an unknown success probability $p$ into a new series with success probability $f(p)$. While theoretically elegant, previous implementations were computationally inefficient, often requiring an excessive number of input bits. We present a "cascading envelope" framework that makes the Bernoulli Factory practical for linear, concave, or convex functions. By using nested approximations and trinomial sampling, our method significantly reduces bit consumption, making it a viable tool for Monte Carlo applications.
Introduction
The Bernoulli Factory problem asks: given a coin with an unknown probability $p$ of landing heads, can we simulate a coin with probability $f(p)$? This is not just a mathematical puzzle; it is a cornerstone of Exact Sampling and Markov Chain Monte Carlo (MCMC) methods, where acceptance probabilities often depend on unknown parameters. However, the "bit-gluttony" of existing methods—requiring tens of thousands of bits for simple functions—has hindered its adoption in real-world computing.
The Cascade Bernoulli Factory
The core innovation of this work is the Cascade Bernoulli Factory. Traditional methods often attempt to fit a single global envelope to the target function $f(p)$. If $p$ is small, these global envelopes are notoriously inefficient.
Our approach utilizes a sequence of nested approximations based on Bernstein polynomials. For concave functions, Jensen’s inequality provides a natural lower bound. We define a sequence of "checkpoints" ($m_1, m_2, \dots$) where the algorithm evaluates whether it has enough information to produce an output.
Trinomial Sampling and Bit Partitioning
At each checkpoint, the algorithm performs "trinomial sampling." It partitions the set of possible bit strings of length $n$ into three categories:
- $A_{n,k}$: Strings that result in an output of 1.
- $B_{n,k}$: Strings that result in an output of 0.
- $C_{n,k}$: Strings that are inconclusive, requiring the algorithm to "continue" to the next checkpoint.
This cascading logic ensures that the algorithm only consumes as many bits as necessary for the specific value of $p$ encountered. It also maintains the "nesting property": if a short bit-string leads to an output, any longer string containing that prefix must lead to the same output. This prevents the need to store massive bit-string tables.
Key Results and Performance
The Cascade method demonstrates a massive reduction in computational overhead compared to previous state-of-the-art methods (e.g., Flegal and Herbei, 2012).
- Initial Bit Cost: For the benchmark "elbow function" $f(p) = \min(2p, 0.8)$, the Cascade method requires only 20 bits to start, whereas previous methods required 256 bits.
- Average Bit Consumption: In simulations with $p=0.01$, our method used an average of 66 bits, compared to over 560 bits for the alternative.
- Scalability: The efficiency gap widens as the problem complexity increases. For a multiplier of $c=20$, the Cascade method starts at 400 bits, while the alternative ballooned to 32,768 bits.
A significant optimization in our method is its behavior at small $p$. For the elbow function, the algorithm can often output a zero on the first round if the initial bit sequence contains no ones—a simple check that drastically improves performance in MCMC applications where $p$ is typically small.
Conclusion
By replacing global envelopes with a cascading series of nested approximations, we have transformed the Bernoulli Factory from a theoretical curiosity into a practical computational tool. The framework is flexible enough to handle various function types and can be coupled with asymptotically efficient methods to provide both practical speed and theoretical robustness. Future work will explore faster convergence for functions with infinite derivatives near zero, such as $f(p) = \sqrt{p}$.
Summary updated