Fast simulation of new coins from old (Q1774211)

The paper is devoted to the problem of fast simulation of new coins from old. In particular, the case of using independent tosses of a coin with probabilities of heads \(p\) to simulate a coin with probabilities of heads \(f(p)\) is constructed, where \(f\) is some unknown function. It is proven that there is a dependence between the properties of the simulation algorithms and classes of functions \(f\). It is shown that the simulation of the given class of functions is equivalent to finding sequences of certain Bernstein polynomials which approximate it from above and below. This construct is used, because the Bernstein polynomials provide exponentially convergent approximations for linear functions. A proof of the fact that any continuous real analytic function bounded away from 0 and 1 has a simulation is given. Necessary conditions for fast simulations are described. A very simple algorithm is given to illustrate the achieved theoretical results. Some open problems are mentioned in the end of the paper.