The Birthday Paradox – how to solve using Python

The Birthday Paradox : in a group of random people, how many people should be in the group in order to find at least two people sharing the same birth date? (Not considering February 29th and assuming birthdays are distributed in equal probability.)

This is the famous Birthday Paradox or the Birthday Problem. In this article, it is discussed how this problem can be build up as an equation and then how to use Python to solve it.

Since an year (not a leap year) has 365 days, it is natural if you think there should be at least 366, so that at least two people share the same birthday. However the answer is surprisingly a smaller value compared to 366.

To solve this problem, following approach can be taken.

If two random people are selected, the probability of not having the same birth date can be calculated as follow:

P2 = (365/365) x (364/365)

Therefore the probability of sharing same birth date is = 1 – P2

In other words, if a person is selected, his birthday can be an any day of the year which is 365/365. Then in order to have a different birthday the next person’s birthday should fall in any day other than the first person’s birthday, there are only 364 selections, hence the probability is 364/365. So when two persons are considered the probability of not sharing the same birthday can be calculated as mentioned above, P2.

When another person (the third one) is considered, the probability would be 363/365.

If it is generalized (let n be the number of people in the group)

P’n = (365/365) x (365-1/365) x (365-2/365) x (365-3/365) …………………. x {[365-(n-1)]/365}

The goal is to find n when Pn is nearly equal to 0 %, in other words 1 – Pn should be nearly equal to 1. Lets take it as .999 or 99.9%

Lets try to simplify the above equation;

P’n = [(1/365)^n] x { 365 x (365-1) x (365-2) ……………………………….. x [365-(n-1)] }

P’n = [(1/365)^n]  x {365 x 364 x 363 x …………………………….. 365 -n +1}

Multiplying with (365 – n)!

P’n =  [(1/365)^n]  x {365 x 364 x 363 x …………………………….. 365 -n +1} x [(365 – n)! / (365 – n)!]

P’n = 365! / [(365^n) x (365 – n)!] ———————(Final Equation)

The final equation can be further simplified in permutation notation as follow (as 365! / (365 – n)! = 365Pn )

bday_problem

Now there is a nice equation,

P’n = 365Pn / 365^n

Then using the final equation, will try to derive the answer.

#!/usr/bin/python

import math as math
import sys

x = math.factorial(365)
ans = 0
disired_probability = 99.9

for i in range (1,366):
    a = 365**i
    b = math.factorial(365-i)
    ans = (1-(x / (a*b)))*100
    if (ans > disired_probability):
        print ('Answer Found - ',i)
        sys.exit()

The answer is 70.

Therefore, in a group of 70 people, there can be two people sharing the same birth date.

This article is licensed under the Creative Commons Attribution-Share Alike 3.0 Unported (CC BY-SA 3.0) license. 
Advertisements

Please add your valuable idea below, will make a discussion, thanks !

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 )

Google+ photo

You are commenting using your Google+ 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 )

w

Connecting to %s