The Birthday Paradox

The Birthday Paradox

BIRTHDAYS!!!! Birthdays make us feel so special...the celebration…the cake…the candles...the balloons... (Of course the Surprise gifts too!!).We had a surprise gift waiting for us a Monday morning. We had Mr. Sudarshan's lecture on Discrete Mathematics and combinatorics. The name of the subject scared us. 'The Pigeon Hole principle', he started. We will try to summarize it for you. Assume there are 6 pigeons and 5 holes. Let us say, each pigeon occupies a hole which means that 5 pigeons occupy the 5 holes and the remaining 1 pigeon has to share a hole with an another one. Hence 2 pigeons share the same hole.

Similarly, consider 365 holes. We need at least 366 pigeons so that one hole is guaranteed to be occupied by 2 pigeons. Let us apply a little transformation to the statement.

Holes : pigeons :: days : people

A simple analogy states that 2 out of 366 people share the same birthday. It seemed clear to us. But he had a different statement to make. He was damn sure that he would find 2 out of 30 randomly chosen people who shared a common birthday. And guess what?? HE WAS RIGHT!! Two of our friends shared a common birthday. While we wondered how this can happen, he was ready with his marker pen to prove his claim. Little did we know that there are mathematical reasons behind it.

Consider there are $N$ number of people around you. What should be the average value of that $N$ so that you can guarantee with more than $50\%$ probability that there at least $2$ people sharing the same birthday?

i.e. Approximately how many people will you choose from a lot, such that you find 2 people with same birthday ?

1. By not considering the leap years

2. Assuming uniform distribution of birthdays throughout the year.

Value of $N$ can be found as follows..

Let us begin by taking a good look at the following equation. Plays an important role u see.. :P

$e=\left(1+\frac{1}{n}\right)^n$

$e^{\frac{1}{n}}=(1+\frac{1}{n})$

$e = \left ( 1-\frac{1}{n} \right )^{-n}$

$e^\frac{-1}{n} = \left ( 1-\frac{1}{n} \right )$

Let us choose one person at a time and compare his birthday with already chosen set of people to see if there is NO match

Select 1^st person out of the $N$ present. Let his name be Mr. Tom. The probability of Mr.Tom

not sharing the same birthday as someone else is 1 i.e. $\frac{365}{365}$. That is obvious isn’t

it?...:) He is the only one selected so far and hence there is no chance of having a match.

Now choose the 2nd person. Let us call him Mr. Jerry. Now there are 2 possibilities.

1. Mr. Jerry sharing the same birthday as Mr. Tom.

2. Mr. Jerry having a different birthday.

Hence the probability of Mr. Jerry NOT having the same birthday as Mr. Tom is product of 2 probabilities

i.e.$\frac{365}{365} \times \left(1 -\frac{1}{365}\right)$

Probability of 1^st person * Probability of 2^nd person

not having same birthday not having the same birthday as the first one

Now choose the 3rd person named Mr. Bluto. With similar reasoning as above, probability of Mr.Bluto not sharing the same birth date is :

$\frac{365}{365} \times \left(1 -\frac{1}{365}\right) \times \left(1 -\frac{2}{365})\right$

Probability of 1^st person * Probability of 2^nd person * Probability of 3^rd person

not having same b'day not having the same b'day not having the same b'day

as the 1^st one as the 1^st one & 2^nd one

The improbability of N person having the same birthday would be:

$\frac{365}{365} \times \left(1 -\frac{1}{365}\right) \times \left(1 -\frac{2}{365}\right) \times \cdots\cdots \times \left(1 -\frac{N-1}{365}\right)$

When the probability of not having the same birthday becomes less than $0.5$, then the probability of having the same birthday becomes dominant..:):)

$\frac{365}{365} \times \left(1 -\frac{1}{365}\right) \times \left(1 -\frac{2}{365}\right) \times \cdots\cdots \times \left(1 -\frac{N-1}{365}\right)\leq 0.5$

The point where this transition occurs gives us our most awaited N...Now now…a little patience there. We still require few more steps to arrive at N…:) Do you remember the equations we asked you to take a good look at? If not please scroll back and check out the equations. We will be using them here…:)

$\frac{365}{365} \times \left(1 -\frac{1}{365}\right) \times \left(1 -\frac{2}{365}\right) \times \cdots\cdots \times \left(1 -\frac{N-1}{365}\right)\leq 0.5$

$1\times e^\frac{-1}{365}\times e^\frac{-2}{365}\times\cdots \times e^\frac{(N-1)}{365}\leq 0.5$

$e^{\frac{-1}{365}\times (1+2+3+\cdots+(N-1))}\leq 0.5$

Apply the following formula to the above equation and let us see what happens.

$1+2+3+\cdots +k = \frac{k(k+1)}{2}$

$e^{\frac{-1}{365} \times {\frac{N(N-1)}{2}}} \leq 0.5$

Applying Logarithms on both sides, we get

$\ln e^{\frac{-1}{365} \times {\frac{N(N-1)}{2}}} \leq \ln 0.5$

$\frac{-1}{365}\frac{N(N-1)}{2} \leq -0.693$

Simplifying it, we get a quadratic equation

$N^2-N-506=0$ (Finding $N$ for $50\%$ probability i.e. considering just the equality )

The roots of this equation are,

$N=23 , -22$

As number of people is a positive quantity, we consider $N=23$.

Voila !!!!!!!!! Here we are…. :) :)

So what’s the moral of the story?? ;)

On an average case, given $23$ members there is $50\%$ probability of you finding $2$ members who share the same birthday…..Amazing isn’t it?..!!!!!!!!!!!!!!!!!!!!!!!

So what are you waiting for??? ;) Go out, make a bet. Tell your friend that you can find $2$ out of $30$ random people(on an average) who share the same birthday. No doubt, you will win it. Get back to us and let us share the money ;)

Three cheers to Math...:) :) :)

By the way, if u reading this today and it happens to be your birthday...Wish you A Very HAPPY BIRTHDAY :)

Shobitha Shetty

Shruthi Nayak