Number of samples needed as input to Bernoulli factory

Question

Let $\{X_i\}$ denote an i.i.d. sequence of Bernoulli variables with parameter $p$. A Bernoulli factory is a procedure that generates events with probability $f(p)$ using the observations $\{X_i\}$, where $f$ is a known function and $p$ is assumed to be unknown.

Is there some general result, or bound, on the number of samples of $\{X_i\}$ needed by a Bernoulli factory?

Some simple examples:

• ($f(p) = p^2$) To generate an event with probability $p^2$ it's sufficient to use two samples of the original sequence $\{X_i\}$. Actually less on average, because if the first of those two samples is $0$ you don't need the second.

• ($f(p) = \sqrt p$) The algorithm at the top of page 7 of this paper generates an event of probability $\sqrt p$. The number of samples of $\{X_i\}$ used by that procedure can be easily computed.

• There are some general approaches for arbitrary $f$, for example this one using martingales.

So, given a function $f$ and a procedure that generates an event that has probability $f(p)$, how can one know if that's the best procedure, in the sense of using the least possible number of observations $X_i$ (on average) that is possible? Or, failing that, are there some bounds on that number?

Answer 1

Two references come to mind:

http://arxiv.org/abs/math/0309222

http://arxiv.org/abs/math/0304143

The gist of it is, if I remember it right, that fast implementation is possible iff f is real-analytic.

Answer 2

I made some progress with this.

Let $N$ be the number of inputs consumed by the Bernoulli factory. If $f$ is differentiable, any factory that is fast in the sense of Nacu-Peres (i.e. $\Pr[N \geq n]$ is exponentially bounded) has $$ \mathrm E[N] \geq (f'(p))^2 \frac{p(1-p)}{f(p)(1-f(p))}. $$ This is theorem 3 from this paper (also on arXiv). The proof is based on the fact that the factory output is a sequential estimator of $f(p)$, to which Wolfowitz's extension of the Cramér-Rao bound can be applied.