Return to Colloquia & Seminar listing
Fast Coin SimulationMathematical Physics & Probability
|Speaker: ||Serban Nacu, UC Berkeley|
|Location: ||693 Kerr|
|Start time: ||Tue, Oct 26 2004, 3:10PM|
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
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.