New Coins From Old, Smoothly

Given a (known) function \(f:[0,1]\to (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_p(N<\infty)\) equal to 1 exists iff \(f\) is continuous. Nacu and Peres (2005) proved that \(f\) is real analytic in an open set \(S\subset (0,1)\) iff such a simulation scheme exists with the probability \(\P_p(N>n)\) decaying exponentially in \(n\) for every \(p\in S\). We prove that for \(\alpha >0\) non-integer, \(f\) is in the space \(C_{\alpha }[0,1]\) if and only if a simulation scheme as above exists with \(\P_p(N>n) \le C (\Delta_n(p))^\alpha\), where \(\Delta_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]\to (0,1)\) is in \(C_{\alpha }[0,1]\) if and only if \(f\) has a series representation \({\sum }_{\infty }^{n=1}F_n\) with \(F_n \in \B_n\) and \({\sum }_{k>n}F_k(x)\leq C({\Delta }_n(x))_{\alpha }\) for all \(x\in [0,1]\) and \(n\geq 1\). We also provide a counterexample to a theorem stated without proof by Lorentz (1963), who claimed that if some \(\phi_n \in \B_n\) satisfy \(|f(x)-{\phi }_n(x)|\leq C({\Delta }_n(x))_{\alpha }\) for all \(x\in [0,1]\) and \(n\geq 1\), then \(f\in C_{\alpha }[0,1]\).