[Math][Python] Birthday problem

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.

(the post first published at 20221221.)


List of my other blog posts.

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.