## 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()
``` >>> 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}) ```