Fast simulation of new coins from old. (English) Zbl 1072.65007

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.


65C50 Other computational problems in probability (MSC2010)
60C05 Combinatorial probability
Full Text: DOI arXiv


[1] Ahlfors, L. V. (1978). Complex Analysis , 3rd ed. McGraw-Hill, New York.
[2] Cover, T. M. and Thomas, J. A. (1991). Elements of Information Theory . Wiley, New York. · Zbl 0762.94001
[3] Durrett, R. (1996). Probability : Theory and Examples . Duxbury Press, Pacific Grove, CA. · Zbl 1202.60001
[4] Elias, P. (1972). The efficient construction of unbiased random sequence. Ann. Math. Statist. 43 865–870. · Zbl 0245.65003
[5] Glynn, P. W. and Henderson, S. G. (2003). Nonexistence of a class of variate generation schemes. Oper. Res. Lett. 31 83–89. · Zbl 1034.65002
[6] Hardy, G. H., Littlewood, J. E. and Pólya, G. (1959). Inequalities. Cambridge Univ. Press. · Zbl 0010.10703
[7] Hoeffding, W. (1963). Probability inequalities for sums of bounded random variables. J. Amer. Statist. Assoc. 58 13–30. · Zbl 0127.10602
[8] Keane, M. S. and O’Brien, G. L. (1994). A Bernoulli factory. ACM Trans. Modeling and Computer Simulation 4 213–219. · Zbl 0844.60008
[9] Knuth, D. E. and Yao, A. C. (1976). The complexity of nonuniform random number generation. In Algorithms and Complexity 357–428. Academic Press, New York. · Zbl 0395.65004
[10] Mossel, E. and Peres, Y. (2002). New coins from old: Computing with unknown bias. Preprint. Available at http://front.math.ucdavis.edu/math.PR/0304143. · Zbl 0997.60052
[11] Peres, Y. (1992). Iterating von Neumann’s procedure for extracting random bits. Ann. Statist. 20 590–597. JSTOR: · Zbl 0754.60040
[12] Tikhomirov, V. M. (1990). Approximation theory. In Analysis II . Encyclopedia of Mathematical Sciences 14 (R. V. Gamkrelidze, ed.) 93–255. Springer, Berlin. · Zbl 0728.41016
[13] von Neumann, J. (1951). Various techniques used in connection with random digits. National Bureau of Standards Applied Math. Series 12 36–38.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.