Sunday, February 7, 2010

Solving the Birthday Problem in Clojure

The Birthday Paradox poses the following question: "How many people do you need in a room for there to be a greater than 50% probability of two people having the same birthday?"
At first guess - it feels big. There are 365 days in a year - so the answer must fall somewhere in the hundreds. (You can read more about the problem on the wikipedia page)
Let's fire up clojure to solve this problem:

C:\clojure-1.1.0>java -cp clojure.jar clojure.main
Clojure 1.1.0
user=> (def +year-size+ 365)
user=> (defn birthday-problem [probability number-of-people]
  (let [new-probability (* (/ (- +year-size+ number-of-people)
    (if (< new-probability 0.5
        (+ 1 number-of-people)
      (birthday-problem new-probability (+ 1 number-of-people)))))
user=> (birthday-problem 1.0 1)
The answer: 23 people! Which when you think about it - rings true when you think of classes at school. There was at least one person who had the same birthday as someone else.
(If you were thinking of a number greater than 100 then you were probably thinking of the number of people you'd need for someone to have the same birthday as you - which is a problem for another day.)

No comments:

Post a Comment