Building a better Bernoulli Factory

09/15/2015 - 12:15pm
09/15/2015 - 1:10pm
Mark Huber (CMC)

Suppose I have a non-fair coin with unknown probability $p$ of heads that I can flip as many times as I'd like. A Bernoulli factory is a way of flipping the coin to construct a single coin flip that has chance $f(p)$ of heads for some function $f(p)$. For example, to get a $p^2(1-p)$-coin, I flip the original coin 3 times, and count it as heads if the sequence is HHT, and tails otherwise. My goal in this talk is to build a fast Bernoulli factory for the innocent looking function $f(p) = Cp$, where $C$ is a given constant. It might look innocent, but it turns out that for a fixed number of coin flips, you cannot build a Bernoulli factory that gives a $Cp$ coin for $C > 1$.

So we're going to use a random number of flips to build our $Cp$-coin. I'll show that when $Cp$ is small, this new method uses (to first order) $C$ flips, which for reasons I'll talk about is probably optimal.

Millikan 2099, Pomona College