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

This question is a continuation of another question of mine, which seeks ways to compute polynomials that converge from above and below to $f$ in a manner that solves the Bernoulli factory problem for $f$. These polynomials form an approximation scheme for $f$. See that question for more details, but here is a recap:

Formal statement: There 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. $0\le a(n, k)\le b(n, k)\le1$,
2. $\lim_{n}g_{n}(\lambda)=\lim_{n}h_{n}(\lambda)=f(\lambda)$ for every $\lambda\in[0,1]$, and
3. for every $m<n$, both $(g_{n} - g_{m})$ and $(h_{m} - h_{n})$ have non-negative coefficients once $g_{n}$, $g_{m}$, $h_{n}$, and $h_{m}$ are rewritten as degree-$n$ polynomials in Bernstein form,

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

It is allowed for $a(n, k)\lt0$ for a given $n$ and some $k$, in which case all $a(n, k)$ for that $n$ are taken to be 0 instead. It is allowed for $b(n, k)\gt1$ for a given $n$ and some $k$, in which case all $b(n, k)$ for that $n$ are taken to be 1 instead.

New coins from old, smoothly

This time, though, we focus on a specific approximation scheme, the one presented by Holtz et al. 2011, in the paper "New coins from old, smoothly".

The scheme involves building polynomials that are shifted upward and downward to approximate $f$ from above and below.

The scheme achieves a convergence rate that generally depends on the smoothness of $f$; in fact, it can achieve the highest convergence rate possible for functions with that smoothness. Roughly speaking, the rate is $O((1/n)^{2(r+\alpha)})$ when $\lambda$ is close to 0 or 1, and $O((1/n)^{r+\alpha})$ elsewhere.

The scheme is as follows:

Let $f$ be a continuous and $r$-times differentiable function—

• that maps [0, 1] to the open interval (0, 1), and
• whose $r$th derivative is $\alpha$-Hölder continuous.

Let $b = 2^s$ and let $s\ge0$ be an integer. Let $Q_{n, r}f$ be a degree $n+r$ approximating polynomial called a Lorentz operator (see the paper for details on the Lorentz operator). Let $n_0$ be the smallest $n$ such that $Q_{n_0, r}f$ has coefficients within [0, 1]. Define the following for every integer $n \ge n_0$ divisible by $n_{0}b$:

• $f_{n_0} = Q_{n_0, r}f$.

• $f_{n} = f_{n/b} + Q_{n, r}(f-f_{n/b})$ for each integer $n > n_0$.

• $\phi(n, \alpha, \lambda) = \frac{\theta_{\alpha}}{n^{\alpha}}+(\frac{\lambda(1-\lambda)}{n})^{\alpha/2}$.

Let $B_{n, k, F}$ be the $k$th coefficient of the degree-$n$ Bernstein polynomial of $F$.

Let $C(\lambda)$ be a polynomial as follows: Find the degree-$n$ Bernstein polynomial of $\phi(n, r+\alpha, \lambda)$, then elevate it to a degree-$n+r$ Bernstein polynomial.

Then the coefficients for the degree $n+r$ polynomial that approximates $f$ are—

• $g(n, r, k) = B_{n+r,k,f_{n}} - D * B_{n+r,k,C}$, and
• $h(n, r, k) = B_{n+r,k,f_{n}} + D * B_{n+r,k,C}$.

The problem here is:

• This method uses three constants, namely $s$, $\theta_{\alpha}$, and $D$, that are vaguely defined in the paper. For example, the paper says only that $D$ should be chosen "large enough".
• The paper has no examples of how the scheme works for a selection of functions $f$, making it hard to understand and apply the Holtz method (especially in an automated way).

Questions

1. What are practical lower bounds for $s$, $\theta_{\alpha}$, and $D$ for the method above, given a function $f$, with or without additional assumptions on $f$? Currently, I care about the following classes of functions: Lipschitz continuous; differentiable; twice differentiable; 4 times differentiable; C1 continuous; C2 continuous; C4 continuous.
2. What are other practical ways to apply the Holtz method to certain functions to find polynomials that converge to those functions?
3. Is the Holtz method with $\alpha=1$ (and thus $r=1$) valid for simulating any Lipschitz continuous or differentiable factory function? (Note that the method as written doesn't apply to non-integer $\alpha$; see also Conjecture 34.)
4. Is the Holtz method with $\alpha=2$ (and thus $r=2$) valid for simulating any twice differentiable factory function?
5. Is the Holtz method with $\alpha=4$ (and thus $r=4$) valid for simulating any four times differentiable factory function?

My Attempt

The Python script lorentz.py shows my attempt to implement the Holtz approximation scheme. It implements an algorithm to toss heads with probability equal to a C2 or C4 continuous piecewise polynomial factory function. However, it relies on an unproven conjecture (Conjecture 34) in the Holtz paper.

Based on this attempt, the C4 continuous case is efficient enough for my purposes, but the case of functions with lesser regularity is not so efficient (such as Lipschitz or C2).

Update (Dec. 4)

Here is my current progress for the Lorentz operator for $\alpha=2$, so $r=2$ (which applies to twice-differentiable functions with Hölder continuous second derivative, even though the paper appears not to apply when $\alpha$ is an integer). Is the following work correct?

The Lorentz operator for $r=2$ finds the degree-n Bernstein polynomial for the target function $f$, elevates it to degree $n+r$, then shifts the coefficient at $k+1$ by $-f\prime\prime(k/n) A(n,k)$ (but the coefficients at 0 and $n+r$ are not shifted this way), where:

$$A(n,k) = (1/(4*n)) * 2 *(n+2-k)/((n+1)*(n+2)),$$

where $k$ is an integer in $[0,n+r]$. Observing that $A(n,k)$ equals 0 at 0 and at $n+r$, and has a peak at $(n+r)/2$, the shift will be no greater (in absolute value) than $A(n,(n+r)/2)*F$, where $F$ is the maximum absolute value of the second derivative of $f(\lambda)$. $A(n,(n+r)/2)$ is bounded above by $(3/16)/n$ for $n\ge 1$, and by $(3/22)/n$ for $n\ge 10$.

Now, find $\theta_\alpha$ for $\alpha=2$, according to Lemma 25:

Let $0<\gamma<2^{\alpha/2}-1$ ($\gamma<1$ if $\alpha=2$).

Solve for $K$: $$(1-(1+\gamma)/2^{\alpha/2} - 4/(4*K)) = 0.$$ The solution for $\alpha=2$ is $K = 2/(1-\gamma)$.

Now find: $$\theta_a = ((4/4)*K^{\alpha/2}/n^\alpha) / ((1-(1+\gamma)/2^\alpha)/n^\alpha)$$ The solution for $\alpha=2$ is $\theta_a = 8/((\gamma-3)*(\gamma-1))$.

For $\gamma=1/100$ and $\alpha=2$, $\theta_a = 80000/29601 \approx 2.703$.

There's no need to check whether the output polynomials have Bernstein coefficients in $(0, 1)$, since out-of-bounds polynomials will be replaced with 0 or 1 as necessary — which is more practical and convenient.

Now all that remains is to find $D$ given $\alpha=2$. I haven't found how to do so yet.

Moreover, there remains to find the parameters for the Lorentz operator when $r>2$. (When $r=0$ or $r=1$, the Lorentz operator is simply the Bernstein polynomial of degree $n$, elevated $r$ degrees to degree $n+r$.)

References

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