Nearly optimal Bernoulli factories for linear functions

Abstract

Suppose that $X_1,X_2,\dots$ are independent identically distributed Bernoulli random variables with mean $p$. A Bernoulli factory for a function $f$ takes as input $X_1,X_2,\dots$ and outputs a random variable that is Bernoulli with mean $f(p).$ A fast algorithm is a function that only depends on the values of $X_1,\dots ,X_T$, where $T$ is a stopping time with small mean. When $f(p)$ is a real analytic function the problem reduces to being able to draw from linear functions $Cp$ for a constant $C>1$. Also it is necessary that $Cp\le 1-\hat{I}\mu$ for known $\hat{I}\mu >0$. Previous methods for this problem required extensive modification of the algorithm for every value of $C$ and $\hat{I}\mu$. These methods did not have explicit bounds on $\text{E}[T]$ as a function of $C$ and $\hat{I}\mu$. This paper presents the first Bernoulli factory for $f(p)=Cp$ with bounds on $\text{E}[T]$ as a function of the input parameters. In fact, ${\sup }_{p\in [0,(1-\hat{I}\mu )/C]}\text{E}[T]\le 9.5C\hat{I}{\mu }^{-1}.$ In addition, this method is very simple to implement. Furthermore, a lower bound on the average running time of any $Cp$ Bernoulli factory is shown. For $\hat{I}\mu \le 1/2$, ${\sup }_{p\in [0,(1-\hat{I}\mu )/C]}\text{E}[T]\ge 0.004C\hat{I}{\mu }^{-1}$, so the new method is optimal up to a constant in the running time.

15 pages; Corrected typo in Theorem 3: changed (1 - γ)^{2} to (1 - γ^{-2}) in the definition of r