2003/09/30 by Serban Nacu, Şerban Nacu, Yuval Peres · 1 citation
Decision Sciences · Mathematics · #Markov Chains and Monte Carlo Methods #Simulation Techniques and Applications #Stochastic processes and statistical mechanics #math.PR #msc:65C50.
paper · pdf · doi:10.1214/105051604000000549
published as Annals of Applied Probability 2005, Vol. 15, No. 1A, 93-115 · Published at http://dx.doi.org/10.1214/105051604000000549 in the Annals of Applied Probability (http://www.imstat.org/aap/) by the Institute of Mathematical Statistics (http://www.imstat.org)
openalex publication_date 2005/02/01 · arxiv created 2005/03/31 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let S⊂(0,1). Given a known function f:S→(0,1), we consider the problem of using independent tosses of a coin with probability of heads p (where p∈S is unknown) to simulate a coin with probability of heads f(p). We prove that if S is a closed interval and f is real analytic on S, then f has a fast simulation on S (the number of p-coin tosses needed has exponential tails). Conversely, if a function f has a fast simulation on an open set, then it is real analytic on that set.