New coins from old, smoothly

DOI10.1007/S00365-010-9108-5MaRDI QIDQ658983zbMATH OpenOpenAlexFDO

Authors Yuval Peres, Olga Holtz, Fedor Nazarov

Publication date 9 February 2012

Published in Constructive Approximation (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial 4.0 International

Full work available at URL https://arxiv.org/abs/0808.1936

zbMATH Keywords

simulationsmoothnessLorentz operatorsBernstein-positive approximation

Mathematics Subject Classification ID

Approximation by polynomials (41A10) Rate of convergence, degree of approximation (41A25)

Abstract: Given a (known) function $f:[0,1]o(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 $Ssubset(0,1)$ iff such a simulation scheme exists with the probability $P_p(N>n)$ decaying exponentially in $n$ for every $pinS$. We prove that for $alpha>0$ non-integer, $f$ is in the space $C^{a}lpha[0,1]$ if and only if a simulation scheme as above exists with $P_p(N>n)leC(Delt{a}_n(p){)}^{a}lpha$, where $Delt{a}_n(x)eqbdmaxsqrtx(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]o(0,1)$ is in $C^{a}lpha[0,1]$ if and only if $f$ has a series representation $su{m}_{n=1}^{i}nfty{F}_n$ with $F_{n}in{B}_n$ and $su{m}_{k>n}{F}_k(x)leC(Delt{a}_n(x){)}^{a}lpha$ for all $xin[0,1]$ and $nge1$. We also provide a counterexample to a theorem stated without proof by Lorentz (1963), who claimed that if some $ph{i}_{n}in{B}_n$ satisfy $|f(x)-ph{i}_n(x)|leC(Delt{a}_n(x){)}^{a}lpha$ for all $xin[0,1]$ and $nge1$, then $fin{C}^{a}lpha[0,1]$.

Recommendations

• Fast simulation of new coins from old
• Versatile Coins
• Optimal coin flipping
• On simulating a class of Bernstein polynomials
• A Bernoulli factory

Cites work

• scientific article; zbMATH DE number 3299651 (Why is no real title available?)
• A Bernoulli factory
• Fast simulation of new coins from old
• Iterating von Neumann's procedure for extracting random bits
• New coins from old: Computing with unknown bias
• The degree of approximation by polynomials with positive coefficients

Cited in

(5)

• Probability, minimax approximation, and Nash-equilibrium. Estimating the parameter of a biased coin
• From the Bernoulli factory to a dice enterprise via perfect sampling of Markov chains
• Versatile Coins
• Fast simulation of new coins from old
• Bernoulli factories and duality in Wright-Fisher and Allen-Cahn models of population genetics

This page was built for publication: New coins from old, smoothly

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q658983)