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 2$) 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?

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?

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$ you use two samples of the original sequence. Actually less, because if the first of those two samples is $0$ you don't need the second.

• ($f(p) = \sqrt 2$) 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 events that have 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$ that is possible? (Of course, the number of required observations may need to be defined in an average sense, since it maybe be random.) Or, failing that, are there some bounds on that number?

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 2$) 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?