Background

We're given a coin that shows heads with an unknown probability, $\lambda$. The goal is to use that coin (and possibly also a fair coin) to build a "new" coin that shows heads with a probability that depends on $\lambda$, call it $f(\lambda)$. This is the Bernoulli factory problem, and it can be solved only for certain functions $f$. (For example, flipping the coin twice and taking heads only if exactly one coin shows heads, we can simulate the probability $2\lambda(1-\lambda)$.)

Specifically, the only functions that can be simulated this way are continuous and polynomially bounded on their domain, and map $[0, 1]$ or a subset thereof to $[0, 1]$, as well as $f=0$ and $f=1$. These functions are called factory functions in this question. (A function $f(x)$ is polynomially bounded if both $f$ and $1-f$ are bounded below by min($x^n$, $(1-x)^n$) for some integer $n$ (Keane and O'Brien 1994). This implies that $f$ admits no roots on (0, 1) and can't take on the value 0 or 1 except possibly at 0 and/or 1.)

In this question, a polynomial $f(x)$ is written in Bernstein form of degree $n$ if it is written as— $$f(x)=\sum_{k=0}^n a_k {n \choose k} x^k (1-x)^{n-k},$$ where $a_0, ..., a_n$ are the polynomial's Bernstein coefficients. The degree-$n$ Bernstein polynomial of $f$ has Bernstein coefficients $f(k/n)$.

Polynomials that approach a factory function

An algorithm simulates a factory function via two sequences of polynomials that converge from above and below to that function. Roughly speaking, the algorithm works as follows:

1. Generate U, a uniform random number in $[0, 1]$.
2. Flip the input coin (with a probability of heads of $\lambda$), then build an upper and lower bound for $f(\lambda)$, based on the outcomes of the flips so far. In this case, these bounds come from two degree-$n$ polynomials that approach $f$ as $n$ gets large, where $n$ is the number of coin flips so far in the algorithm.
3. If U is less than or equal to the lower bound, return 1. If U is greater than the upper bound, return 0. Otherwise, go to step 2.

The result of the algorithm is 1 with probability exactly equal to $f(\lambda)$, or 0 otherwise.

However, the algorithm requires the polynomial sequences to meet certain requirements; among them, the sequences must be of Bernstein-form polynomials that converge from above and below to a factory function. See the formal statement, next.

Formal Statement

More formally, there must exist two sequences of polynomials, namely—

• $g_{n}(\lambda): =\sum_{k=0}^{n}a(n, k){n \choose k}\lambda^{k}(1-\lambda)^{n-k}$, and
• $h_{n}(\lambda): =\sum_{k=0}^{n}b(n, k){n \choose k}\lambda^{k}(1-\lambda)^{n-k}$,

for every integer $n\ge1$, such that—

1. $a(n, k)\le b(n, k)$,
2. $\lim_{n}g_{n}(\lambda)=\lim_{n}h_{n}(\lambda)=f(\lambda)$ for every $\lambda\in[0,1]$, and
3. $(g_{n+1}-g_{n})$ and $(h_{n}-h_{n+1})$ can be rewritten as degree-$(n+1)$ polynomials with non-negative Bernstein coefficients,

where $f(\lambda)$ is continuous on $[0, 1]$ (Nacu and Peres 2005; Holtz et al. 2011), and the goal is to find the appropriate values for $a(n, k)$ and $b(n, k)$.

On Condition 3

Condition 3 is also known as a "consistency requirement"; it ensures that not only the upper and lower polynomials "decrease" and "increase" to $f(\lambda)$, but also their Bernstein coefficients do as well. This requirement is crucial in the algorithm I mentioned above.

Condition 3 is equivalent in practice to each of the following (Nacu and Peres 2005; Farouki and Rajan 1988):

• For every integer $k\in[0,2n]$ and every integer $n>=1$ that's a power of 2, $a(2n, k)\ge\sum_{i=\max(0, k-n)}^{\min(k, n)}a(n, i){n \choose i}{n \choose k-i}/{2n \choose k}$ and $b(2n, k)\le\sum_{i=\max(0, k-n)}^{\min(k, n)}b(n, i){n \choose i}{n \choose k-i}/{2n \choose k}$.

• For every integer $k\in[0,2n]$ and every integer $n>=1$ that's a power of 2, $a(2n, k)\ge\mathbb{E}[a(n, X)]$ and $b(2n, k)\le\mathbb{E}[b(n, X)]$, where $X$ is a hypergeometric($2n$, $k$, $n$) random variable.

• For every integer $k\in[0, n+1]$ and every integer $n>1$, $a(n, k) = (k/n)*a(n-1, \max(0, k-1)) + ((n-k)/n)*a(n-1, \min(n-1, k))$ and $b(n, k) = (k/n)*b(n-1, \max(0, k-1)) + ((n-k)/n)*b(n-1, \min(n-1, k))$

A useful technique is to bound— $$|E(W_n(X/n)) - W_n(k/(2n))| \le \phi(f, n),$$ for every integer $k\in[0,2n]$ and every integer $n>=1$ that's a power of 2 (Nacu and Peres 2005), where—

• $W_n$ is a function whose Bernstein polynomial approximates $f$ (and $W_n$ can equal $f$),
• $X$ is a hypergeometric($2n$, $k$, $n$) random variable, and
• $\phi$ is a function that depends on $f$ and $n$.

Then, for certain choices of $\phi$, condition 3 will be met if the following series converges: $$\sum_{m\ge\log_2(n)}\phi(f, 2^m).$$ See Theorem 1 of "Proofs for Polynomial Building Schemes" for details.

Building Polynomials

One way to meet the formal statement above is to generate an approximating polynomial of a continuous factory function $f(\lambda)$ of each degree $n$, then shift that polynomial upward and downward by the error needed to approximate $f$.

There are results in the literature that give bounds on the error when approximating a function with polynomials. However, these results are generally too tight to be used in the Bernoulli factory problem.

An example follows for Bernstein polynomials. Let $B_n(f)$ be the Bernstein polynomial of $f$ of degree $n$. Then if $f$ has a Lipschitz continuous derivative with Lipschitz constant $L$, then— $$|B_n(f(\lambda)) - f| \le L \lambda(1-\lambda)/(2n) \le L/(8n)$$ (Lorentz 1966), and the upper and lower polynomials' coefficients would be formed as $a(n,k) = f(k/n) - L/(8n)$ and $b(n,k) = f(k/n) + L/(8n)$.

It can be shown that this error bound ($L/(8n)$) does not meet condition 3 of the formal statement for functions with Lipschitz continuous derivative (see "Failures of the Consistency Requirement".)

However, a slightly looser error bound does meet that condition, namely, $L/(7n)$ for $n\ge 4$. See Theorem 3 of "Proofs for Polynomial Building Schemes".

And in fact, the sum $\sum_{m\ge\log_2(n)} L/(8\cdot 2^m) = L/(4n)$ (see Theorem 1 mentioned earlier) is looser than $L/(7n)$ and thus likewise meets condition 3.

A Conjecture

This suggests an easy way to modify error bounds on polynomials in Bernstein form that approximate $f$ in order to satisfy the Bernoulli factory requirements of the formal statement.

Let $f(\lambda):[0,1]\to(0,1)$ have $r\ge 1$ continuous derivatives, and denote the Bernstein polynomial of degree $n$ of a function $g$ as $B_n(g)$. For each integer $n\ge1$ that's a power of 2, let $W_n(\lambda)$ be a function with a known Bernstein polynomial. ($W_n$ can but need not equal $f$.)

For each such $n$, suppose that there is $D>0$ such that— $$|f(\lambda)-B_n(W_n(\lambda))| \le DM/n^{r/2},$$ whenever $0\le \lambda\le 1$ and $M$ is the maximum absolute value of $f$ and its derivatives up to the $r$-th derivative.

Then, a conjecture is that there is $C_0$ greater than 0 such that for every $C\ge C_0$, there are polynomials $g_n$ and $h_n$ (for each $n\ge 1$) as follows:

1. $g_n$ and $h_n$ have Bernstein coefficients $W_n(k/n) - CM/n^{r/2}$ and $W_n(k/n) + CM/n^{r/2}$, respectively ($0\le k\le n$), if $n$ is a power of 2, and $g_n=g_{n-1}$ and $h_n=h_{n-1}$ otherwise;
2. $\lim_n g_n =\lim_n h_n=f$;
3. $(g_{n+1}-g_{n})$ and $(h_{n}-h_{n+1})$ can be rewritten as degree-$(n+1)$ polynomials with non-negative Bernstein coefficients.

(2 and 3 correspond to the formal statement above.)

It is also conjectured that the same value of $C_0$ suffices when $f$ has a Lipschitz continuous $(r-1)$-th derivative and $M$ is the maximum absolute value of $f$ and the Lipschitz constants of $f$ and its derivatives up to the $(r-1)$-th derivative.

Here are results that correspond to the conjecture.

• If $r=1$ and $W_n=f$, then $C_0 = (1+\sqrt{2})$ (Nacu and Peres 2005), even in the Lipschitz case.
• If $r=2$ and $W_n=f$, then $C_0 = 1/2$ (Nacu and Peres 2005).
• If $r=2$ and $W_n=f$, then $C_0 = 1/7$ for every $n\ge 4$ (see "Proofs for Polynomial Building Schemes").

Here are some conjectured results (for others see "A Conjecture on Polynomial Approximation"). They relate to polynomials that achieve a better convergence rate than Bernstein polynomials (namely $O(1/n^{r/2})$ rather than $O(1/n)$), such as those discussed in Micchelli (1973), Guan (2009), Güntürk and Li (2021), Holtz et al. (2011), and Draganov (2014).

• If $r=3$ and $W_n=2 f - B_n(f)$*, then $C_0 = \frac{3}{16-4 \sqrt{2}}.$
• If $r=5$ and $W_n = B_n(B_n(f))+3(f-B_n(f))$**, then $C_0 = 0.27.$

The following questions relate to the conjecture:

1. For what value of $C_0$ is the conjecture true when $W_n = 2 f - B_n(f)$ and $r$ is 3 or 4? Interesting functions $f$ to test are quadratic polynomials.

2. For what value of $C_0$ is the conjecture true when $W_n$ is arbitrary?

Remarks

• Related question: https://math.stackexchange.com/questions/3904732/what-are-ways-to-compute-polynomials-that-converge-from-above-and-below-to-a-con
• This question is one of numerous open questions about the Bernoulli factory problem. Answers to them will greatly improve my pages on Bernoulli factories.

References

• Łatuszyński, K., Kosmidis, I., Papaspiliopoulos, O., Roberts, G.O., "Simulating events of unknown probabilities via reverse time martingales", arXiv:0907.4018v2 [stat.CO], 2009/2011.
• Keane, M. S., and O'Brien, G. L., "A Bernoulli factory", ACM Transactions on Modeling and Computer Simulation 4(2), 1994.
• Holtz, O., Nazarov, F., Peres, Y., "New Coins from Old, Smoothly", Constructive Approximation 33 (2011).
• Nacu, Şerban, and Yuval Peres. "Fast simulation of new coins from old", The Annals of Applied Probability 15, no. 1A (2005): 93-115.
• Farouki, R.T., and Rajan, V.T., "Algorithms for polynomials in Bernstein form", Computer Aided Geometric Design 5(1), 1988.
• C.S. Güntürk, W. Li, "Approximation of functions with one-bit neural networks", arXiv:2112.09181 [cs.LG], 2021.
• G.G. Lorentz, "Approximation of functions", 1966.
• Micchelli, C. (1973). The saturation class and iterates of the Bernstein polynomials. Journal of Approximation Theory, 8(1), 1-18.
• Guan, Zhong. "Iterated Bernstein polynomial approximations." arXiv preprint arXiv:0909.0684 (2009).
• Draganov, Borislav R. "On simultaneous approximation by iterated Boolean sums of Bernstein operators." Results in Mathematics 66, no. 1 (2014): 21-41.

* Corresponds to the iterated Bernstein polynomial of order 2 (Güntürk and Li 2021).

*** Corresponds to the iterated Bernstein polynomial of order 3 (Güntürk and Li 2021).