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.

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 )

Google photo

You are commenting using your Google 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 )

Connecting to %s

%d bloggers like this: