Coin Flips

February 24, 2015

I decided over the weekend to perform a simple test over several random number generators at my disposal; the test counts the number of “heads” that appear in a million flips. Here’s the test:

(do ((n 1000000 (- n 1)))
     (h 0 (if (< (rand 1.0) 0.5) (+ h 1) h)))
    ((zero? n) h))

Applied to the random number generator built-in to Chez Scheme, I get these five results: 500017, 500035, 499968, 499977, and 500009. That’s pretty close to perfect. The random number generator in the Standard Prelude isn’t as good: 499987, 500503, 500422, 499808, and 500264. And the simple linear-congruential random number generator (69069 x + 1234567) % 232 gives these results: 500301, 499445, 500232, 500047, and 498341.

None of those results are unusual (well, maybe the Chez result is too close to perfection), but that’s not what interests us today. What we want to do is assume that the random number generator is biased but still use it to make an unbiased coin flip. Say you have a coin that returns 40% heads and 60% tails. To get an unbiased coin result, flip the coin twice; if you get two heads or two tails, flip twice more, but if you get opposite results, return the first.

Your task is to write a program that delivers unbiased coin flips from a biased coin. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

3 Responses to “Coin Flips”

  1. Graham said

    My second common lisp submission in as many days! I won’t be able to keep up this pace, unfortunately.

  2. Mike said
    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 toss
    

    examples:

    >>> 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})

  3. dan pink said

    (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).

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: