## Birthday Paradox

### October 12, 2012

In the study of probability, the Birthday Paradox states that in a group of 23 people, there is a 50% chance that two will have the same birthday; in a group of 57 people, the odds rise to 99%.

Your task is to simulate the birthday paradox over many trials and verify the odds. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Advertisements

Pages: 1 2

[…] today’s Programming Praxis exercise, our goal is to simulate the well-known birthday paradox. Let’s […]

My Haskell solution (see http://bonsaicode.wordpress.com/2012/10/12/programming-praxis-birthday-paradox/ for a version with comments):

Should one not allow for leap years?

Here is a video explaining birthday paradox: http://www.numberphile.com/videos/23birthday.html

A Python version

import random as RA

import itertools as IT

def analytic(N):

prob = 1

for i in range(0, N):

prob *= (1.0 – i / 365.0)

return 1 – prob

def gen_cases(N):

while 1:

yield [RA.randint(1, 365) for i in range(N)]

def monte_carlo(N, mcsamples = 1000):

“””calculate chance that 2 or more people have same birthday”””

cnt = sum(len(c) != len(set(c)) for c in IT.islice(gen_cases(N), mcsamples))

return cnt / float(mcsamples)

#[/sourcecode]

Repost. A python version.

A Python version which takes into account leap years, 0-364 are the non-leap days of the year and 365 is Feb 29th:

Hah, beat you to one for once. :)

Here’s a post that I wrote a week and a half ago on my own birthday that basically works out the math behind the problem and then lets you run a simulation build into the web page (Javascript w/ JQuery). You can choose any number of birthdays to simulate and it will generate that many for you over the next year, keeping statistics for each number, along with the expected value. I think it’s pretty neat at least. :)

Check it out here: The Birthday Paradox

Clojure solution.

Solution written in Go (source code https://gist.github.com/3885112):

package main

import (

"fmt"

"math/rand"

)

func main() {

fmt.Printf("Chance of same birthday in group with 23 people: %.0f%%\n", getChanceOfSameBirthdayInGroup(23)*100)

fmt.Printf("Chance of same birthday in group with 57 people: %.0f%%\n", getChanceOfSameBirthdayInGroup(57)*100)

}

func getChanceOfSameBirthdayInGroup(groupSize uint) float32 {

n := 10000

numberOfSameBirthdays := 0

for i := 0; i < n; i++ {

if isSameBirthdayInGroup(groupSize) {

numberOfSameBirthdays++

}

}

return float32(numberOfSameBirthdays) / float32(n)

}

func isSameBirthdayInGroup(groupSize uint) bool {

birthdays := make(map[int]uint8)

for i := uint(0); i < groupSize; i++ {

birthday := rand.Intn(365)

birthdays[birthday]++

if birthdays[birthday] == 2 {

return true

}

}

return false

}

A year whose number is divisible by 100 is not a leap year, unless it is also divisible by 400. So the year 2000 was a leap year, but the year 2100 won’t be. A program trying to calculate birthday statistics for people currently alive can ignore this issue, but if it’s supposed to work across history it needs to take it into account. Of course, if one goes back before the Gregorian calendar was adopted, matters get extremely complicated, and figuring out how to deal with the eventual breakdown (at some not-yet-predictable time) of the Gregorian calendar is even trickier.

A Java Solution:

Leap years? Not sure what leap years have to do with the original problem stated in the main blog homepage. Here is my PHP solution for the first part.

for($i = 1; $i < 1000; $i++)

{

$arr = array();

for($q = 0; $q 1) { $total++; }

}

echo $total / 1000;

Not sure what’s wrong with your blog but it just can’t off half my code. Forget this. Moving on.

[…] Pages: 1 2 […]