Python: Getting a Fair Flip out of an Unfair Coin
If you have an unfair coin (i.e. one that favors heads or tails), how do generate a fair flip (i.e. one that doesn't favor heads or tails)? My buddy Hy Carrinski and I came up with the following algorithm:
"""Get a fair flip out of an unfair coin."""
from collections import defaultdict
from random import random
FLIP_RATIO = 0.7
def flip_unfair_coin():
"""Flip an unfair coin. Return a boolean."""
return random() > FLIP_RATIO
def create_fair_flip():
"""Generate a fair flip. Return a boolean."""
while True:
flip = flip_unfair_coin()
if flip != flip_unfair_coin():
return flip
# Demonstrate that it works.
if __name__ == '__main__':
results = defaultdict(int)
for i in xrange(1000000):
results[create_fair_flip()] += 1
percentage = (results[False] / float(results[False] + results[True])) * 100
print "Percentage heads:", percentage
Comments
While we're at it, there's a typo in the script: you write "Prove" but you merely demonstrate.
heads/heads = 0.49
heads/tails = 0.21
tails/heads = 0.21
tails/tails = 0.09
The algorithm throws away heads/heads and tails/tails and returns tails for heads/tails and heads for tails/heads - each with a probability of of 0.21 per attempt (with transparent re-tries for the rejected cases).
@Dirk: it works because even biased coin flips are still independent. (if they are not e.g. if a person is controlling the flips, or the coin has been set to do a certain sequence, this method will fail).
Essentially, you are flipping the coin twice, and then only looking at the times when the two results are different. The first time you get that scenario, pick the first result (or last, it doesn't matter). The probability of getting Heads then Tails is the same as the probability of getting Tails then Heads (due to independence), so you get odds of 50% for the overall result being Heads or Tails.
Updated. Thanks.
Wow, great explanation!
Nice job providing the reference. I'm 100% okay with the fact that I came up with the same thing as Von Neumann ;)