Return to Question

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 $P(x)$ is written in Bernstein form of degree $n$ if it is written as— $$P(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 an arbitrary function $f(\lambda)$ has Bernstein coefficients $f(k/n)$. In general, this Bernstein polynomial differs from $f$ even if $f$ is a polynomial.

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})$ are polynomials with non-negative Bernstein coefficients once they are rewritten to polynomials in Bernstein form of degree exactly $n+1$,

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 the following statement (Nacu & Peres 2005). For every integer $k\in[0,2n]$ and every integer $n\ge 1$ that's a power of 2, $a(2n, k)\ge\mathbb{E}[a(n, X_{n,k})]$ and $b(2n, k)\le\mathbb{E}[b(n, X_{n,k})]$, where $X_{n,k}$ is a hypergeometric($2n$, $k$, $n$) random variable.

A useful technique is to bound— $$|\mathbb{E}(W_n(X_{n,k}/n)) - W_{2n}(k/(2n))| \le \phi(f, n),$$ for every integer $k\in[0,2n]$ and every integer $n\ge 1$ that's a power of 2 (Nacu and Peres 2005, especially (10) and (11)), where—

• $W_{2^0}(\lambda), W_{2^1}(\lambda), ..., W_{2^i}(\lambda),...$ is a sequence of functions on [0, 1] that converge uniformly to $f$,
• $X_{n,k}$ is a hypergeometric($2n$, $k$, $n$) random variable, and
• $\phi$ is a function that depends on $f$ and $n$.

I believe bounding the expression above can help solve the conjecture stated later in this post; see another MathOverflow question of mine on this.

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)$. Let $W_{2^0}(\lambda), W_{2^1}(\lambda), ..., W_{2^i}(\lambda),...$ be a sequence of functions on [0, 1] that converge uniformly to $f$.

Here are results that correspond to the conjecture.

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.

• Ł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).

A Conjecture

In the following, a polynomial $P(x)$ is written in Bernstein form of degree $n$ if it is written as— $$P(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 an arbitrary function $f(\lambda)$ has Bernstein coefficients $f(k/n)$. In general, this Bernstein polynomial differs from $f$ even if $f$ is a polynomial.

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)$. Let $W_{2^0}(\lambda), W_{2^1}(\lambda), ..., W_{2^i}(\lambda),...$ be a sequence of functions on [0, 1] that converge uniformly to $f$.

Without loss of generality: For what value of $C_0$ is the conjecture true when $W_n = 2 f - B_n(f)$ and $r$ is 3 or 4? When $W_n$ is arbitrary?

Background

I asked this question in order to solve the so-called Bernoulli factory problem, described next. 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 if $f$ is continuous (Keane and O'Brien 1994).

However, since I asked this question I have found a Bernoulli factory algorithm that I believe is general enough to cover all the cases that this conjecture would help solve.

Since this conjecture may be of broader interest, though, I leave this question open. See also my other open questions about the Bernoulli factory problem.

Results

Here are results that correspond to the conjecture.

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 linear combinations (Butzer 1953) and iterated Boolean sums (Micchelli 1973) of Bernstein polynomials.

• 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.$

• Keane, M. S., and O'Brien, G. L., "A Bernoulli factory", ACM Transactions on Modeling and Computer Simulation 4(2), 1994.
• Nacu, Şerban, and Yuval Peres. "Fast simulation of new coins from old", The Annals of Applied Probability 15, no. 1A (2005): 93-115.
• C.S. Güntürk, W. Li, "Approximation of functions with one-bit neural networks", arXiv:2112.09181 [cs.LG], 2021.
• Micchelli, C. (1973). The saturation class and iterates of the Bernstein polynomials. Journal of Approximation Theory, 8(1), 1-18.
• Butzer, P.L., "Linear combinations of Bernstein polynomials", Canadian Journal of Mathematics 15 (1953).

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

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

Equivalently, there is $C_1>0$ such that, for each integer $n\ge 1$ that's a power of 2— $$\max_{0\le k\le 2n}\left|\left(\sum_{i=0}^k \left(W_n\left(\frac{i}{n}\right)\right) {n\choose i}{n\choose {k-i}}/{2n \choose k}\right)-W_{2n}\left(\frac{k}{2n}\right)\right|\le \frac{C_1 M}{n^{r/2}},$$ so that $C=\sum_{m\ge \log_2(n)} C_1 M/2^{mr/2}$.

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.

Equivalently (see also Nacu and Peres 2005), there is $C_1>0$ such that, for each integer $n\ge 1$ that's a power of 2— $$\max_{0\le k\le 2n}\left|\left(\sum_{i=0}^k \left(W_n\left(\frac{i}{n}\right)\right) {n\choose i}{n\choose {k-i}}/{2n \choose k}\right)-W_{2n}\left(\frac{k}{2n}\right)\right|\le \frac{C_1 M}{n^{r/2}}.$$

It is also conjectured that the same value of $C_0$ (or $C_1$) 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.

Equivalently, there is $C_1>0$ such that, for each integer $n\ge 1$ that's a power of 2— $$\max_{0\le k\le 2n}\left|\left(\sum_{i=0}^k \left(W_n\left(\frac{i}{n}\right)\right) {n\choose i}{n\choose {k-i}}/{2n \choose k}\right)-W_{2n}\left(\frac{k}{2n}\right)\right|\le \frac{C_1 M}{n^{r/2}},$$ so that $C=\sum_{m\ge \log_2(n)} C_1 M/2^{mr/2}$.