Coin Flips
February 24, 2015
We begin by writing a function that delivers a biased coin flip, assuming an unbiased random-number generator in the underlying language; we return 1 with probability 0.4, else 0:
(define (biased) (if (< (rand) 0.4) 1 0))
To show that the coin is biased, sum a million flips:
> (do ((n 1000000 (- n 1))
(s 0 (+ s (biased))))
((zero? n) s))
399633
Now to turn a biased coin into an unbiased coin, examine two successive flips:
(define (unbiased)
(if (zero? (biased))
(if (zero? (biased)) (unbiased) 0)
(if (zero? (biased)) 1 (unbiased))))
> (do ((n 1000000 (- n 1))
(s 0 (+ s (unbiased))))
((zero? n) s))
500085
And now we have an unbiased coin flip from a biased coin.
That isn’t just useful when you know your coin is biased. If you have an unknown random number generator, instead of relying on it being unbiased, you can guarantee for yourself that it is unbiased.
You can run the program at http://ideone.com/ItjdVe.
My second common lisp submission in as many days! I won’t be able to keep up this pace, unfortunately.
from random import random class Coin: def __init__(self, bias=0.4): self.bias = bias def flip(self): return 'Heads' if random() < self.bias else 'Tails' def unbiased_flip(self): toss = self.flip() while toss == self.flip(): toss = self.flip() return tossexamples:
>>> from collections import Counter
>>> coin = Coin()
>>> Counter(coin.flip() for _ in range(100000))
Counter({'Tails': 59775, 'Heads': 40225})
>>> Counter(coin.unbiased_flip() for _ in range(100000))
Counter({'Tails': 50220, 'Heads': 49780})
>>> coin = Coin(0.25)
>>> Counter(coin.flip() for _ in range(100000))
Counter({'Tails': 75179, 'Heads': 24821})
>>> Counter(coin.unbiased_flip() for _ in range(100000))
Counter({'Tails': 50122, 'Heads': 49878})
(1) why do you say that the results from the “standard prelude” aren’t as good?
(What is the average deviation expected, for the sum of a million items each 0 or 1?. I would guess it is 500,000 divided by the sqrt of a million, i.e. 500).