Making black boxes out of black boxes

Omiros Papaspiliopoulos gave a talk yesterday at the Big MC seminar on “Making black boxes out of black boxes – the Bernoulli Factory problem and its applications”, inspired by this paper with Latuszynski et al..

The problem is very easy to state: suppose you have a p-coin (i.e. which has probability p of landing on Heads), where p is unknown. How can you use that coin to simulate from a Bernoulli(f(p)), where f is some function? You can toss the coin as many times as you need.

If you choose the constant function f(p)=1/2, the problem is quite easy, and from there, you can get any other constant function. The class of functions for which a solution exists is quite large and includes, for example, f(p)=p/2. However, amazingly, there is no algorithm which works for f(p)=\min(1,2p). This statement provoked some disbelief in the audience, and several of us tried (and failed) to prove Omiros wrong while he was giving details of the proof, which is quite technical.

The second part of the seminar was a nice presentation by Pierre Jacob on Andrieu et al.’s paper on Particle Markov Chain Monte Carlo which was read at the RSS last autumn.



Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: