Posts Tagged ‘paradox’

Programming Praxis – Birthday Paradox

October 12, 2012

In today’s Programming Praxis exercise, our goal is to simulate the well-known birthday paradox. Let’s get started, shall we?

Some imports:

import Control.Monad
import Data.List
import System.Random

A single run consists of assigning each person a birthday (assuming they are distributed uniformly throughout the year) and checking whether there are any duplicates.

paradox :: Int -> IO Bool
paradox n = fmap (\g -> or [elem h t | (h:t) <- tails . take n $
            randomRs (1, 365 :: Int) g]) newStdGen

Determining the chance that a given population shares a birthday is a matter of running the test a large number of times and returning the percentage of cases in which a birthday is shared.

trial :: Int -> IO Float
trial = fmap ((/ 100) . genericLength . filter id) . replicateM 10000 . paradox

We have to run the test for a group of 23 people (50% chance) and 57 people (99% chance).

main :: IO ()
main = do print =<< trial 23
          print =<< trial 57

A random trial run produces 50.38% and 99.03%, respectively, which are close enough to confirm the birthday paradox.