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](http://www.math.chalmers.se/~wastlund/coinFlip.pdf) 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](http://arxiv.org/abs/0907.4018) 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?



Number of samples needed as input to Bernoulli factory
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.


