×

zbMATH — the first resource for mathematics

New coins from old, smoothly. (English) Zbl 1238.41007
Given a coin with unknown probability of heads \(p\), as well as a fair coin, the authors would like to simulate a coin with probability of heads \(f(p)\), where \(f:[0,1]\to (0,1)\) is a known function. First, the authors define the simulation rate for a simulation algorithm. Next, they recall some basic results regarding Bernstein polynomials, Bernstein basis, Bernstein coefficients, Bernstein-positive consistent approximation from below, Bernstein-positive consistent approximation from above. The relationship between Bernstein-positive approximation and smoothness is then established. Next, Lorentz operators and simultaneous approximation are examined. An iterative construction of Bernstein-positive consistent approximations schemes is very clean presented. Finally, the authors prove that G. G. Lorentz’s Claim 10 [Math. Ann. 151, 239–251 (1963; Zbl 0116.04602)] is invalid.

MSC:
41A10 Approximation by polynomials
41A25 Rate of convergence, degree of approximation
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] DeVore, R.A., Lorentz, G.G.: Constructive Approximation. Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 303. Springer, Berlin (1993)
[2] Keane, M.S., O’Brien, G.L.: A Bernoulli factory. ACM Trans. Model. Comput. Simul. 4(2), 213–219 (1994) · Zbl 0844.60008
[3] Lorentz, G.G.: The degree of approximation by polynomials with positive coefficients. Math. Ann. 151, 239–251 (1963) · Zbl 0116.04602
[4] Lorentz, G.G.: Bernstein Polynomials, 2nd edn. Chelsea Publishing, New York (1986)
[5] Mossel, E., Peres, Y.: New coins from old: computing with unknown bias. Combinatorica 25(6), 707–724 (2005). With an appendix by C. Hillar · Zbl 1099.68052
[6] Nacu, Ş., Peres, Y.: Fast simulation of new coins from old. Ann. Appl. Probab. 15(1A), 93–115 (2005) · Zbl 1072.65007
[7] Peres, Y.: Iterating von Neumann’s procedure for extracting random bits. Ann. Stat. 20(1), 590–597 (1992) · Zbl 0754.60040
[8] Timan, A.F.: Theory of Approximation of Functions of a Real Variable. Dover, New York (1994). Translated from the Russian by J. Berry. Translation edited and with a preface by J. Cossar. Reprint of the 1963 English translation
[9] von Neumann, J.: Collected Works. Vol. V: Design of Computers, Theory of Automata and Numerical Analysis. Pergamon Press, The Macmillan, New York (1963). General editor: A.H. Taub · Zbl 0188.00104
[10] Williams, D.: Probability with Martingales. Cambridge Mathematical Textbooks, Cambridge University Press, Cambridge (1991)
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.