Skip to content
Permalink
master
Switch branches/tags

Name already in use

A tag already exists with the provided branch name. Many Git commands accept both tag and branch names, so creating this branch may cause unexpected behavior. Are you sure you want to create this branch?
Go to file
 
 
Cannot retrieve contributors at this time
executable file 91 lines (61 sloc) 1.79 KB
#!/usr/bin/env python
""" Empirically simulate the birthday paradox
The birthday paradox is the surprisingly high change that two
people in a group of people share the same birthday.
See https://en.wikipedia.org/wiki/Birthday_problem for details.
"""
import random
from matplotlib import pyplot as plt
import numpy as np
NUMBER_OF_SIMULATIONS = 100000
def simulate_number_of_people_in_room_before_collision():
"""
:return: Number of people added to room to achieve first collision
:rtype: int
"""
unique_birthdays = set()
all_birthdays = []
while True:
birthday_ordinal = random.randint(0, 365 - 1)
unique_birthdays.add(birthday_ordinal)
all_birthdays.append(birthday_ordinal)
if len(unique_birthdays) != len(all_birthdays):
return len(all_birthdays)
def generate_histogram(s):
plt.hist(
s,
bins=xrange(max(s)),
color='green',
)
plt.ylabel('Number of simulations')
plt.xlabel('Number of people in room when first birthday collision occurs')
plt.axvline(
float(sum(s)) / NUMBER_OF_SIMULATIONS,
color='red',
linewidth=2,
linestyle='--'
)
plt.show()
def generate_cdf(s):
normed_counts, bin_edges = np.histogram(s, bins=max(s), normed=True)
cdf = np.cumsum(normed_counts)
plt.plot(
bin_edges[1:],
cdf,
linewidth=2,
)
plt.ylabel('CDF')
plt.xlabel('Number of people in room when first birthday collision occurs')
plt.axhline(
.5,
color='red',
linewidth=2,
linestyle='--'
)
plt.show()
simulations = [
simulate_number_of_people_in_room_before_collision()
for _ in xrange(0, NUMBER_OF_SIMULATIONS)
]
generate_histogram(simulations)
generate_cdf(simulations)