Puzzle time - biased to fair coin

[Klaus]

You have a biased coin where heads has probability p and tail has probability 1-p (p is unknown).

Let's say you need a fair coin flip. How can you use the biased coin to simulate a fair coin?

[Horace]

exactly, precisely, 50/50?

[Klaus]

Yes.

[Horace]

Without allowing for infinite flips, I don't see how it's possible.

[jon-nyc]

:::

You just need two events that occur with equal probability. So do pairs of flips. H-T will occur with equal probability as T-H.

:::

[Horace]

@jon-nyc said in Puzzle time - biased to fair coin:

:::

In the general case, that still requires an unbounded number of flips. Imagine a highly, highly biased coin. But, I do take the meaning that you can keep flipping it twice till you get h/t or t/h in a pair of flips.

:::

[jon-nyc]

Another method but it only works if you know p.

:::

Consider H and T as denoting bits 1 and 0 respectively.

Imagine randomly generating a number between 0 and 1 using flips of the coin to generate bits after the “decimal” place.

There has to be a median value x such you are equally likely to generate a number above x as generating one below x (assume infinite number of flips so the probability of generating x is 0).

So flip the coin until you deviate above or below the binary expansion of x. Above is heads, below is tails.

:::

[jon-nyc]

I'm sure that method has a much lower number of expected flips than the H-T/T-H method. At least for coins with a decent bias.

[Klaus]

@jon-nyc said in Puzzle time - biased to fair coin:

:::

You just need two events that occur with equal probability. So do pairs of flips. H-T will occur with equal probability as T-H.

:::

Yes. And if H-H or T-T occur, you ignore the attempt and make another trial (it's important to make a new trial; just going on until HT or TH occurs won't work). The idea stems from von Neumann.

[Klaus]

@jon-nyc said in Puzzle time - biased to fair coin:

I'm sure that method has a much lower number of expected flips than the H-T/T-H method. At least for coins with a decent bias.

Check out the "Iterated von Neumann extractor". It allows you to get arbitrarily close to extracting all the entropy in the biased coin flips. It's quite simple. You can generate a new biased sequence from the existing one. For instance, the sequence of discarded vs non-discarded pairs, or the sequence of which pair was discarded (e.g. generate H for HH and T for TT) yields another biased coin flips. When using these sources of randomness in the same way, one can iterate arbitrarily.

[jon-nyc]

@jon-nyc said in Puzzle time - biased to fair coin:

I'm sure that method has a much lower number of expected flips than the H-T/T-H method. At least for coins with a decent bias.

It’s fairly straightforward to show that the expected number of flips to get a non-biased result using the official answer is 1/(p*(1-p)). And the expected number of flips using the binary representation method is half of that, or 1/(2p*(1-p))