You and a friend have a tie-breaker that needs to be decided with coin tosses. You know the coin will land on heads 75% of the time, and your friend gets to pick heads or tails. How can you ensure that the results are fairer than 75% heads?

A solution is to toss more than once. Imagine two tosses. The possible outcomes are:

• heads then heads; probability is 0.75*0.75, or 0.5625
• heads then tails; probability is 0.75*0.25, or 0.1875
• tails then heads; probability is 0.75*0.25, or 0.1875
• tails then tails; probability is 0.25*0.25, or 0.625

1. Toss twice
2. If heads then tails, or tails then heads, stop and use the first result (heads or tails)
3. else, start over at step 1

Congratulations...you have an unbiased result.

Thinking for a moment though...what if you keep getting 'heads then heads' or 'tails then tails'. It's theoretically possible for this to continue until you die. That isn't good, so how can you break out of it?

Say you want to run enough rounds to ensure that the expected bias is less than 51% heads. How can you get to that?

The first round stopped (18.75% + 18.75%), or 37.5% of the time. The second round occurs 62.5% of the time. If you have a second round, it will stop there 37.5% of the time and continue 62.5% of the time. Thus, it will stop in the first round 37.5% of the time and in the second round 62.5%*37.5%, or 23.4% of the time. Continuing this and using p as the probability of heads (p = 75% in our problem), you end up with:

If we plot that vs # of rounds for p = 0.75 (75% chance of heads), we get:

What overall chance of heads does that give us after n rounds? We found earlier that stopping in one of the rounds means a 50% chance of heads. We also found an equation for the probability of hitting a stopping condition after n rounds. We were given in the problem statement that the default is 75% heads. Thus, we multiply the probability of stopping after n rounds by 50%, and the probability of continuing after n rounds by 75%. That is:

Plotting that vs # of rounds for p = 0.75 (75% chance of heads), we get:

You originally wanted to reduce the overall chance of heads to less than 51%. From the last equation, you have to go through at least 7 rounds to do that.