Programming Praxis – Birthday Paradox

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.

Tags: , , , , , , ,

Leave a Reply

Fill in your details below or click an icon to log in: Logo

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