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.

About these ads

Tags: , , , , , , ,

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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 )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


Follow

Get every new post delivered to your Inbox.

Join 35 other followers

%d bloggers like this: