A practical implementation of the bernoulli factory

A Practical Implementation of the Bernoulli Factory
Andrew C. Thomas∗ Jose H. Blanchet† August 25, 2011

arXiv:1106.2508v2 [stat.AP] 24 Aug 2011

Abstract The Bernoulli Factory is an algorithm that takes as input a series of i.i.d. Bernoulli random variables with an unknown but fixed success probability p, and outputs a corresponding series of Bernoulli random variables with successprobability f (p), where the function f is known and defined on the interval [0, 1]. While several practical uses of the method have been proposed in Monte Carlo applications, these require an implementation framework that is flexible, general and efficient. We present such a framework for functions that are either strictly linear, concave, or convex on the unit interval using a series of envelope functionsdefined through a cascade, and show that this method not only greatly reduces the number of input bits needed in practice compared to other currently proposed solutions for more specific problems, but can easily be coupled to more asymptotically efficient methods to allow for theoretically strong results.

1

Introduction

First made explicit by Keane and O’Brien [1994], a Bernoulli Factory isdefined as an algorithm that takes as its input an i.i.d. sequence of Bernoulli random variables with unknown success probability – call this pin – and outputs a new sequence of Bernoulli random variables whose success probability, pout , is a known function of the input probability. A Bernoulli Factory does not use any approximation for either pin or pout , instead obtaining output draws through astochastic process with two absorbing states, one of which has terminal probability pout . The prototypical problem for this comes from von Neumann [1951], which seeks to generate a “fair coin”, or a draw from a Be(0.5) random variable, from an i.i.d. sequence of Bernoullis with unknown success probability p. The corresponding stochastic process has three states, labelled “yes”, “no” or “continue”: •Begin in state “continue”.
∗ †

Department of Statistics, Carnegie Mellon University. Corresponding author; email act@acthomas.ca Department of Industrial Engineering and Operations Research, Columbia University.

1

• Take two draws from the input sequence. The possible outcomes are grouped as {00, 01, 10, 11}. • While the outcome is 00 or 11, remain in state “continue”. Discard these bitsand replace them with two new draws. • If the outcome is 10, output “yes”; if the outcome is 01, output “no”. Because both 01 and 10 have probability p(1 − p) or occurring, there is equal probability of the outcome being a “yes” or a “no”, and as a result, the outcome can be likened to the flip of a fair coin. The running time of this method is two times a Geometric random variable with successprobability 2p(1 − p), so that the expected number of input bits required is 1 . p(1−p) A similar process can be conducted to turn a series of fair coins into a coin with any success probability pout , by noting that a uniform random variable can be produced through the representation
∞

U=
i=1

2−i Xi

where Xi ∼ Be(0.5). However, a finite number of bits will be needed if the outcome ofinterest is specified as Y = I(U < pout ). The stochastic process has an unbounded number of states, but is as simple to specify as the standard von Neumann example: • Begin with n = 1. • At each stage n, set Un =
n i=1

2−i Xi . Note that Un ≤ Un+k for all n and k.

• If Un > p, then U > p as well; output “no”. • If p − Un < 2n−1 , then no matter what the remaining inputs are, U < p; output “yes”.• Otherwise, add one more digit to the expansion and repeat the previous three steps. These algorithms each converge in geometric time, with rates proportional to the target probability pout . While neither requires a sophisticated implementation in order to produce a correct output, these methods suggest a general trend: that methods that produce absorbing states of simple Markov chains...