Event Type:

Department Colloquium

Date/Time:

Friday, April 20, 2007 - 08:00

Location:

Kidd 364

Guest Speaker:

Institution:

École Normale Supérieure, Paris

Abstract:

You are given a coin with probability of heads p, where p is unknown. Can you use it to simulate a fair coin? How about a coin with probability of heads 2p? Or a coin with probability of heads f(p), where f is a known function? For a fair coin, the problem goes back to Von Neumann in the 1950s. 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 is small, in the sense that its distribution has exponential tails. When does a function have a fast simulation?

Surprisingly, it turns out this happens if and only if the function is real analytic. This is an instance of a more general phenomenon: there is a connection between the computational and analytic/algebraic properties of certain systems. 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.