Puzzle time - biased to fair coin
-
wrote on 15 May 2021, 21:34 last edited by
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?
-
wrote on 15 May 2021, 21:42 last edited by
exactly, precisely, 50/50?
-
wrote on 15 May 2021, 22:18 last edited by
Yes.
-
wrote on 15 May 2021, 23:35 last edited by
Without allowing for infinite flips, I don't see how it's possible.
-
wrote on 16 May 2021, 00:54 last edited by
:::
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.
:::
-
:::
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.
:::
wrote on 16 May 2021, 00:58 last edited by 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.
:::
-
wrote on 16 May 2021, 02:10 last edited by
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.
:::
-
wrote on 16 May 2021, 02:11 last edited by 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.
-
:::
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.
:::
wrote on 16 May 2021, 10:26 last edited by 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.
-
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.
wrote on 16 May 2021, 16:32 last edited by@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.
-
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.
wrote on 17 May 2021, 00:45 last edited by@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))