# How to generate randomness using a biased coin? [closed]

Imagine we have three people and we want to select one of them at random.

If we had a fair coin we could have tossed the coin twice to get one of the 4 outcomes and could have related the occurrence of any three of them with the first, second and third person..

How can we do this if we have a biased coin instead?

• It isn't at all clear what you're actually asking, and, as I suspect this is homework or self-study, you should add the self-study tag. – jbowman Mar 31 '18 at 18:31
• stats.stackexchange.com/questions/50295/… – whuber Mar 31 '18 at 20:43

One way to do this, is by what is known as the von-Neumann trick.

Imagine you have a biased coin where you get heads($H$) with probability $p$ and tails($T$) with probability $1-p$. Notice that if you throw the coin twice, the outcomes $HT$ and $TH$ are equiprobable with probability $p(1-p)$. You can simulate a fair coin by assigning the outcome $HT$ to $H$ and the outcome $TH$ to $T$. If you get one of the other two cases($HH$ or $TT$) you ignore them and repeat the experiment.

Now that you know how to simulate a fair coin, you can easily extend this to simulate throwing a fair coin multiple times by repeating the above experiment.

Note that this method can be very inefficient, especially when $p$ approaches $1$ e.g $p=0.99$. Since you are waiting for the first event $HT$ or $TH$, you are wasting a lot of throws since those two events only occur with probability $p(1-p)=0.0099$ each.

• Mathematically correct...but practicality is unclear. ¿What if $p=99.99999\%$? That seems like a long time to wait for a TH or HT – Gregg H Mar 31 '18 at 18:40
• Yes indeed I should add that the method is inefficient. – Andreas G. Mar 31 '18 at 18:41
• I hope the moderators would agree a smiley emoji would be appropriate here. – Gregg H Mar 31 '18 at 18:44
• :) :) :) :) :) :) – Andreas G. Mar 31 '18 at 18:47
• @Mark L. Stone If it's homework, they are only hurting themself. Nevertheless, it's not clear(at least to me) that this is a homework exercise. – Andreas G. Mar 31 '18 at 19:16