Fast simulation of new coins from old

Abstract

Let S\subset (0,1). Given a known function f:S\to (0,1), we consider the problem of using independent tosses of a coin with probability of heads p (where p\in 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.

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)

Cited by in corpus (22)

• Provable Quantum Advantage in Randomness Processing
• On nonnegative unbiased estimators
• Exact Simulation for Multivariate Itô Diffusions
• Experimental Quantum Randomness Processing
• Exact sampling for intractable probability distributions via a Bernoulli factory
• Nearly optimal Bernoulli factories for linear functions
• Generalized Speedy Q-learning
• An Experimental Quantum Bernoulli Factory
• Modular Quantum-to-Quantum Bernoulli Factory in an Integrated Photonic Processor
• An asymptotically optimal Bernoulli factory for certain functions that can be expressed as power series
• Perfect simulation using atomic regeneration with application to Sequential Monte Carlo
• General Quantum Bernoulli Factory: Framework Analysis and Experiments
• A Practical Implementation of the Bernoulli Factory
• New coins from old, smoothly
• Efficient Bernoulli factory MCMC for intractable posteriors
• An Efficient $\epsilon$-BIC to BIC Transformation and Its Application to Black-Box Reduction in Revenue Maximization
• Simulating Events of Unknown Probabilities via Reverse Time Martingales
• The Fundamental Theorem of Perfect Simulation
• Simulating a coin with irrational bias using rational arithmetic
• Black-box constructions for exchangeable sequences of random multisets
• Complexity and multi-functional variants of the Quantum-to-Quantum Bernoulli Factories
• Designing Perfect Simulation Algorithms using Local Correctness