This is even simpler explanation of the Birthday problem.
Such problems are abundant in textbooks about probability. A pair of dice is rolled. What is the probability that the two dice show the same number?
Three/four/etc dice are rolled. Same question.
Let's solve this by experiment. Pair of dice:
#!/usr/bin/env python3
total=0
at_least_one_pair=0
for i in range(6):
for j in range(6):
total=total+1
if i==j:
at_least_one_pair=at_least_one_pair+1
print (i, j, "one pair")
else:
print (i, j, "different")
print ("total", total)
print ("at_least_one_pair", at_least_one_pair)
print ("probability", at_least_one_pair/total)
The probability is \( \frac{1}{6} \).
3 dice?
#!/usr/bin/env python3
total=0
at_least_one_pair=0
for i in range(6):
for j in range(6):
for k in range(6):
total=total+1
if i==j or j==k or i==k:
at_least_one_pair=at_least_one_pair+1
print (i, j, k, "at least one pair")
else:
print (i, j, k, "all different")
print ("total", total)
print ("at_least_one_pair", at_least_one_pair)
print ("probability", at_least_one_pair/total)
... total 216 at_least_one_pair 96 probability 0.4444444444444444
4 dice?
#!/usr/bin/env python3
total=0
at_least_one_pair=0
for i in range(6):
for j in range(6):
for k in range(6):
for m in range(6):
total=total+1
if i==j or i==k or i==m or j==k or j==m or k==m:
at_least_one_pair=at_least_one_pair+1
print (i, j, k, m, "at least one pair")
else:
print (i, j, k, m, "all different")
print ("total", total)
print ("at_least_one_pair", at_least_one_pair)
print ("probability", at_least_one_pair/total)
... total 1296 at_least_one_pair 936 probability 0.7222222222222222
Now generalize this problem to 365-sided dice. And throw 23 such dices.
#!/usr/bin/env python3
import random
def random_lst(l, m):
return [random.randint(0, m-1) for i in range(l)]
for i in range(10000):
sample=random_lst(23, 365)
l=len(set(sample))
if l==23:
print ("all different", sample)
else:
print ("coincidences ", sample)
% python3 4.py | grep coinc | wc -l 5105
Rougly \( \frac{1}{2} \), as stated in Wikipedia
70 dices?
#!/usr/bin/env python3
import random
def random_lst(l, m):
return [random.randint(0, m-1) for i in range(l)]
for i in range(10000):
sample=random_lst(70, 365)
l=len(set(sample))
if l==70:
print ("all different", sample)
else:
print ("coincidences ", sample)
According to Wikipedia, 99.9%:
% python3 5.py | grep coinc | wc -l 9994
Now about birthday attack.
Yes, I know about these lousy Disqus ads. Please use adblocker. I would consider to subscribe to 'pro' version of Disqus if the signal/noise ratio in comments would be good enough.