Fairness Through Unfairness

How math can help you make an unfair coin… fair

Photo by Shaojie on Unsplash

Assume that it is unimaginably important to play a round of “Heads or Tails?”. Naturally, a fair coin — one that turns Heads or Tails roughly with the same frequency in the long run — is required. However, further assume that you are only given an unfair coin, say one that turns “Heads” about 70% of the times and “Tails” the rest 30%.

So, what can we do to play that so much wanted round of “Heads or Tails”?

Forging Fairness

We can clearly forge our way to a fair round of “Heads or Tails” by melting that unfair coin and then crafting a new, well-balanced, and fair one. However, since it is unsurprisingly more probable for a reader of this post to be proficient at Math rather than iron forging, we shall not delve into more details about that.

So, back to coin-tossing, what we actually want is to simulate the toss of a fair coin by using an unfair one. Evidently, this simulation will require us to flip our coin more than once, so, let us try to mathematically formulate what we want to do.

At first, let us denote by p the probability with which our unfair coin yields “Heads”. So, in our above example, we would have p=0.70. Next, we have to describe what a “fair coin toss” would look like, using our unfair coin. Let us assume that, for instance, a “fair coin toss” — FCT, for short — consists of tossing our unfair coin twice and keeping the last result. We should prove, then, that this FCT is, well, fair. That is, we have to prove that it yields Heads or Tails with equal probability — we shall write FCT results in italics, to distinguish them from the unfair ones.

So, let us compute the probability to have Heads in a FCT. Since we are interested in the result of the last coin toss, we have two cases of interest:

• The first toss might be Heads followed by a second Heads toss. That can happen — assuming that naturally each coin toss is independent of any other — with probability 0.7 x 0.7 = 0.49.
• The second toss might well be Tails with probability 0.3, so in this case the probability to have Heads in the second toss is 0.3 x 0.7 = 0.21.
• Then, the total probability to have Heads in the second toss, i.e., to have Heads as a result in our FCT is 0.21 + 0.49 = 0.70.

Yeah… This did change exactly nothing. But, isn’t it interesting that we got 0.7 as a result for our FCT? Well, not that much, if you think of it for a bit. In our calculations we have assumed that each toss is independent of each other, i.e., there is no interference among any two different tosses. So, essentially, the probability to have Heads as a result in any toss is the same — 0.7 in our case.

So, there is no way to forge our fair coin by just considering a sequence of independent tosses as a single FCT.

But, then, what else could we do?

Refining Fairness

The major problem in our rationale so far is that each toss is independent of each other, so we have actually no chance to get something better than what we already had. But, what if we make the following minor change in our definition of a FCT:

• We make two coin tosses and note down their results.
• In case the first one is Tails but the second one is Heads, we say the FCT result is Heads.
• In case the first one is Heads but the second one is Tails, we say the FCT result is Tails.
• If both tosses have the same result, we repeat the above.

Okay, we have indeed refined our definition of a FCT. The idea behind the above process is that, under the above, Heads and Tails have the same probability to occur, i.e., 0.3 x 0.7 = 0.21. So, in that sense, the two interesting results of FCT appear at the same frequency. Also, observe how in the improbable case we get two tails (0.3 x 0.3 = 0.09), or the much more frequent case we get two heads (0.7 x 0.7 = 0.49), we proceed as if nothing significant has happened. That way, we “ignore” our coin’s unfairness, trying to favor balanced pairs of coin tosses more than imbalanced ones.

Okay, but, does all this really work?

Well, you know, this means we have to try to prove it. So, as before, let us compute the probability for Heads:

• There is the case that we have a pair of Tails-Heads (in that order) with the first pair of tosses, which happens with probability 0.3 x 0.7 = 0.21.
• There is the case that we have a pair of Tails-Heads for the first time in our second pair of tosses, i.e., the first pair is either Heads-Heads or Tails-Tails (0.7 x 0.7 + 0.3 x 0.3 = 0.58) and then the second one is Tails-Heads (0.3 x 0.7 = 0.21), so, in total 0.58 x 0.21 = 0.1218.
• In a similar fashion, the desired result might come in the third pair, with probability 0.58 x 0.58 x 0.21 = 0.070644.
• …

In general, one might reach the desired Tails-Heads pair for the first time after n steps, where the first n-1 steps are of the form Heads-Heads or Tails-Tails. The probability to reach that n-th step, as you might well suspect is given by:

Nice an neat result.

So, the total probability that we get Heads in our FCT is:

Okay, this seems easy to compute, right?

The above is nothing more but a mere geometric series, so we can make some further computations as follows:

Amazing! We got this!

Okay, that is really reassuring. We got exactly what we wished for, so we can go and take a power nap…

But, does this really work?

We got the result we wanted to but, well, we did so for a very specific case. In the general case, it would be nice to have the same result hold for any coin that yields Heads with probability p and Tails with probability 1-p. In that case, using the same simulation process as before, the probability to get Heads at the n-th step is given by:

Just let p = 0.7 and everything is the same as above.

So, the total probability for our coin to turn Heads in a FCT is:

Yeap, we did it again!

Perfect, exactly as above, we got a fair “coin” for any unfair one — but for the extreme cases when p=0 or p=1.

Conclusions

We managed to show that there is a way to simulate a fair coin with an arbitrarily unfair one. While simple in its key ideas, there is a deeper layer into that approach. Indeed, what we managed to do above was to interweave some independent events — in that case, the tosses of the unfair coin — in such a way that we managed to essentially wipe out their independence.

At this point, a question arises. Is there something special with 1/2? In other words, could we, given a coin that yields Heads with probability p, simulate any other coin that yields Heads with probability q? In other words, given an unfair coin, do we have full control over its unfairness or are we doomed to just convert it to a fair one?