Waste less time on Facebook — follow Brilliant.

Fair Coin Toss

Suppose you are the referee of a football game (whether it is the NFL or the EPL) and you are asked to toss a coin to determine which team chooses which side etc. Most coins are slightly biased so how do you use a flawed coin to generate a perfectly fair event, i.e., an event with probability 1/2? Here is a procedure that will work. In theory it is not finite and could go on forever, but probability theory tells us that the chance is very high that the procedure will terminate in a few steps.

So what is the method? Suppose your coin is biased towards Heads with probability \(\alpha\). So the probability of Tails is \(1 - \alpha\). Here \(\alpha\) is any real number between 0 and 1. Then perform the following procedure: Toss the coin twice. Of the four outcomes, HH, HT, TH, TT, only HT and TH are considered valid outcomes. Note that by the independence of the Bernoulli trials that is tossing a coin, the probability of tossing HT is \(\alpha\cdot (1 - \alpha)\) while the probability of tossing TH is \((1 - \alpha)\cdot \alpha\) which is exactly the same! So we narrow our sample space to these two equally likely events and that represents probability 1/2 each.

What if we tossed HH or TT instead? Then discard the outcome and start over i.e., toss the coin two more times. If we regard a "successful" experiment as one that yields one of HT or TH, then the probability of a successful experiment is \(2\alpha(1- \alpha)\) while the probability of failure is \(\alpha^2 + (1 - \alpha)^2\). So, on average, how many tries before we conclude our experiment successfully? This is given by the expected value of the geometric distribution where we keep keep tossing the coin twice until we succeed. The expected value is \(\frac{1}{2 \alpha (1 - \alpha)}\). This could be large is \(\alpha\) is small; for example, if \(\alpha = 0.1\), then this expected value is around 5.55 i.e., closer to 6 double tosses. But for most reasonable coins, this will be close to 2 or 3.

So next time you need to decide something fair, you know what to do!

Note by Krishnan Shankar
1 year, 5 months ago

No vote yet
1 vote


There are no comments in this discussion.


Problem Loading...

Note Loading...

Set Loading...