New coins from old, smoothly
Given a (known) function f:[0,1]→(0,1), we consider the problem of simulating a coin with probability of heads f(p) by tossing a coin with unknown heads probability p, as well as a fair coin, N times each, where N may be random. The work of Keane and O'Brien (1994) implies that such a simulation scheme with the probability ¶p(N<∞) equal to 1 exists iff f is continuous. Nacu and Peres (2005) proved that f is real analytic in an open set S⊂(0,1) iff such a simulation scheme exists with the probability ¶p(N>n) decaying exponentially in n for every p∈S. We prove that for α>0 non-integer, f is in the space Cα[0,1] if and only if a simulation scheme as above exists with ¶p(N>n)≤C(Δn(p))α, where $Δ_n(x)\eqbd \max \{\sqrt{x(1-x)/n},1/n \}$. The key to the proof is a new result in approximation theory: Let $\B_n$ be the cone of univariate polynomials with nonnegative Bernstein coefficients of degree n. We show that a function f:[0,1]→(0,1) is in Cα[0,1] if and only if f has a series representation ∑n=1∞Fn with $F_n \in \B_n$ and ∑k>nFk(x)≤C(Δn(x))α for all x∈[0,1] and n≥1. We also provide a counterexample to a theorem stated without proof by Lorentz (1963), who claimed that if some $ϕ_n \in \B_n$ satisfy ∣f(x)−ϕn(x)∣≤C(Δn(x))α for all x∈[0,1] and n≥1, then f∈Cα[0,1].
