Q: A conjecture on consistent monotone sequences of polynomials in Bernstein form 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:

*

*Generate U, a uniform random number in $[0, 1]$.

*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.

*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—

*

*$a(n, k)\le b(n, k)$,

*$\lim_{n}g_{n}(\lambda)=\lim_{n}h_{n}(\lambda)=f(\lambda)$ for every $\lambda\in[0,1]$, and

*$(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$.
For each integer $n\ge 1$ that's a power of 2, 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\ge D$ such that for every $C\ge C_0$, there are polynomials $g_n$ and $h_n$ (for each $n\ge 1$) as follows:

*

*$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;

*$\lim_n g_n =\lim_n h_n=f$;

*$(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$.

(2 and 3 correspond to the formal statement above.)
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.

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:

*

*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.


*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).
