The Birthday Paradox

Posted: April 18, 2009 in logic, mathematics, paradox
Tags: ,

This is one theory that really interested me. Can you guess what is the probability that any two people in a football court ,out of a total of 23 including the referee,share the same birthday. It is more than 50 %. Atleast we have mathematical proof for that.

The actual statement is “In a group of at least 23 randomly chosen people, there is more than 50% probability that some pair of them will both have been born on the same day. For 57 or more people, the probability is more than 99%, and it reaches 100% when the number of people reaches 367 (there are a maximum of 366 possible birthdays)”.This happens because we have to consider the total number of pairs in the field rather than the number of players on the field.

Suppose when there are n players there can be n.(n-1)/2 pairs. So with 23 players there can be 23×11,ie 253 pairs possible. Now we can see how does it calculate the probability. Let the probability that atleast one pair of them share  a birthday be p(n). Then the probability that all the birthdays are on different dates is 1-p(n) which we can call as ~p(n).

Now if n>365, Pigeonhole principle shows that ~p(n) is 0. If n<365, then:

~p(n)= 365/365 x 364/365 x 363/365 x …… x (365-n-1)/365,

since the second person cant have the birthday of the first and third person cant have the birthday same as 1st or second.

=> ~p(n)= 365! / ((365^n).(365-n)!)

Keeping in mind that p(n)=1-~p(n),if we substitute values for n, then we get :

p(23)=50.7%

p(57)=99%

p(367)=100%

Now that was a simple proof right. And this theory is the basis of the famous birthday attack( Given a function f, the goal of the attack is to find two inputsx1,x2 such that f(x1) = f(x2).) in cryptography.

PS: In reallife there are a lot more parameters that affect the result like  leap years, twins, seasonal or weekday variations.

Advertisements

Leave a Reply

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 )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s