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 -coin (i.e. which has probability of landing on Heads), where is unknown. How can you use that coin to simulate from a , where is some function? You can toss the coin as many times as you need.
If you choose the constant function , 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, . However, amazingly, there is no algorithm which works for . 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.