Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

You are given a coin with probability of heads p, where p is unknown. Can you use it to simulate a coin with probability of heads 2p? This question was raised by Asmussen in 1991, motivated by an application in the simulation of renewal processes. More generally, if f is a known function, can you use a coin with probability of heads p (p unknown) to simulate a coin with probability of heads f(p)? In 1994, Keane and O'Brien obtained necessary and sufficient conditions for a function f to have such a simulation. We are looking at the problem of efficient simulation. Let N be the number of p-coin tosses required to simulate a f(p)-coin toss. Typically N will be random; we say the simulation is fast if N has exponential tails. We prove that a function f has a fast simulation if and only if it is real analytic. The proof is constructive, and leads to algorithms that can be implemented. We use tools from the theory of large deviations, approximation theory, and complex analysis. This is joint work with Yuval Peres.