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 (ACM Trans. Model. Comput. Simul. 4(2):213–219, 1994) implies that such a simulation scheme with the probability ℙ _p (Nn) decaying exponentially in n for every p∈S. We prove that for α>0 noninteger, 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 varDelta _n(x):=max{Ö{x(1-x)},1}varDelta _{n}(x):=max{sqrt{x(1-x)},1}. The key to the proof is a new result in approximation theory: Let B+_nmathcal{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¥F_nsum_{n=1}^{infty}F_{n} with F_n Î B+_nF_{n}in mathcal{B}^{+}_{n} and ∑ _k>n F _k (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 (Math. Ann. 151:239–251, 1963), who claimed that if some j_n Î B+_nvarphi_{n}inmathcal{B}^{+}_{n} satisfy |f(x)−φ _n (x)|≤C(Δ _n (x)) α for all x∈[0,1] and n≥1, then f∈C α [0,1].