Have I mentioned that I’m a sucker for probability puzzles? I found this one at ibbly.com:

Two teams from opposite ends of the country have been drawn to play each other in a competition. They need to determine which team plays at home and do so fairly at a distance. They decide to try to generate a 50:50 probability from the following week’s UK national lottery draw.

The lottery draw consists of drawing 7 balls from 49.

To make the situation clear, there are 49 balls, labeled 1-49. The balls are thoroughly mixed, and 7 are drawn at random.

The author of ibbly.com points out that a very simple (and incorrect) approach to generating a 50:50 distribution is use the parity of the first ball drawn. Let’s simulate the process in Clojure.

``````(defn balls [n]
"Random shuffle of the integers 1 ... n, inclusive"
(shuffle (range 1 (inc n))))  ;;shuffle introduced in version 1.2

(defn lottery [] (take 7 (balls 49)))

(defn trial []
(first (lottery)))

(defn trials [n]
(let [outcomes (take n (repeatedly trial))
odds (count (filter odd? outcomes))]
(float (/ odds n))))
``````

The results of the simulation confirm the expected bias, given that 25 of the 49 balls are odd: ``` ```

``````(trials 100000)
0.51156
user> (float (/ 25 49))
0.5102041``````

So, how do we use the lottery drawing to simulate a fair coin? The author of ibbly.com proposes a somewhat complicated method:

We know that there are C(49,6)=13,983,816 ways of drawing 6 balls from 49. This is an even number so there's definitely a way of describing a 50% probability, even if it involves writing down 6,991,908 combinations explicitly. But can we find a more succinct way?

It turns out that such an approach is possible. A bit of trial and error shows that there's exactly a 50% chance that the lowest of the six main balls is one of {2,3,4,5,6,15,16,17,21,36,39,41,43,44}.

I'm not even going to think about that. There is a much simpler way to simulate the coin toss. Here's the code, with an explanation following.

``````(defn trial-adjusted []
(let [draw (lottery)
fst (first draw)
snd (second draw)]
(if (= 1 fst) snd fst)))``````

We go back to the parity approach, but we fix the sample space. The original approach uses 25 odd balls and 24 even ones, introducing a bias in favor of odd. We simply throw out one of the odd balls by disregarding it. I chose "1", but it does not matter which of the odd balls is thrown out. Simulation confirms the bias is gone.

``````user> (binding [trial trial-adjusted] (trials 100000))
0.50057``````