8
$\begingroup$

Main Question

Suppose $f:[0,1]\to[0,1]$ is continuous, polynomially bounded, and belongs to a large class of functions (for example, the $k$-th derivative, $k\ge 0$, is continuous, Lipschitz continuous, concave, strictly increasing, bounded variation, or in the Zygmund class). 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).

Then find a non-negative random variable $X$ and a non-trivial series $f(\lambda)=\sum_{a\ge 0}\gamma_a(\lambda)$ such that $\gamma_a(\lambda)/\mathbb{P}(X=a)$ (letting 0/0 equal 0) has a simple Bernoulli factory algorithm (and is preferably a polynomial or rational function with rational Bernstein coefficients lying in $[0, 1]$).

  • An example of $X$ is $\mathbb{P}(X=a) = p (1-p)^a$ where $0 < p < 1$ is a known rational. That is, the probability of getting $a$ is $p (1-p)^a$.
  • The convergence rate must be $O(1/n^{r/2})$ if the class has only functions with Lipschitz-continuous $(r-1)$-th derivative. The method may not introduce transcendental or trigonometric functions (as with Chebyshev interpolants).

A special case of this turns out to boil down to the following question.

Given $r\gt 0$ and $C\gt 0$, for which value of $p$ ($0\lt p\lt 1$), if any, does the following inequality hold true? $$ C/2^{(a+b)r} \le p(1-p)^a,$$ where $a\ge 0$ is an integer and $b\ge 0$ is the smallest integer that satisfies $C/2^{(a+b)r} \le p$.

See the edit history for details on this special case.

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 question would help solve.

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

General and Related Questions

The following questions relate to the main question above.

  • Special case: Let $f(\lambda):[0,1]\to [0,1]$ be writable as $f(\lambda)=\sum_{n\ge 0} a_n \lambda^n,$ where $a_n\ge 0$ is rational, $a_n$ is nonzero infinitely often, and $f(1)$ is irrational. Then what are simple criteria to determine whether there is $0\lt p\lt 1$ such that $0\le a_n\le p(1-p)^n$ and, if so, to find such $p$? Obviously, if $(a_n)$ is nowhere increasing then $1\gt p\ge a_0$.
  • Prove or disprove: Given that $f:[0,1]\to (0,1]$ is convex, the polynomials $(g_n) = (B_n(f) - \max_{0\le\lambda\le 1}|B_n(f)(\lambda)-f(\lambda)|)$ (where $n\ge 1$ is an integer power of 2) are in Bernstein form of degree $n$, converge to $f$ from below, and satisfy: $(g_{2n}-g_{n})$ is a polynomial with non-negative Bernstein coefficients once it's rewritten to a polynomial in Bernstein form of degree exactly $2n$. The same is true for the polynomials $(g_n) = (B_n(f) - |B_n(f)(1/2)-f(1/2)|)$, if $f$ is also symmetric about 1/2.

References

  • Keane, M. S., and O'Brien, G. L., "A Bernoulli factory", ACM Transactions on Modeling and Computer Simulation 4(2), 1994.
$\endgroup$

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.