simulate a fair coin in at most N flips. For how many values of p is this possible?

Question

Mathematician John von Neumann is credited with figuring out how to take a biased coin (whose probability of coming up heads is p, not necessarily equal to 0.5) and “simulate” a fair coin. Simply flip the coin twice. If it comes up heads both times or tails both times, then flip it twice again. Eventually, you’ll get two different flips — either a heads and then a tails, or a tails and then a heads, with each of these two cases equally likely. Once you get two different flips, you can call the second of those flips the outcome of your “simulation.”



For any value of p between zero and one, this procedure will always return heads half the time and tails half the time. This is pretty remarkable! But there’s a downside to von Neumann’s approach — you don’t know how long (i.e., how many flips) the simulation will last.

Suppose I want to simulate a fair coin in at most three flips. For which values of p is this possible?

Extra credit: Suppose I want to simulate a fair coin in at most N flips. For how many values of p is this possible?

Answer 1

The expected value is Np