My Weblog

Blog about programming and math

Birthday Paradox

Two years ago i came to this problem in cryptography class when mine prof was dealing with some sort of collision in hash function. At that time i was not interested in probability but after solving couple of Project Euler problems, had some thought about it. According to Wikipedia , the birthday problem, or birthday paradox pertains to the probability that in a set of randomly chosen people some pair of them will have the same birthday.It also says that according to pigeonhole principal when 366 th person enters the room , the probability reach the 100% [ Assuming there are only 365 days in year]. The question is , what is the value of N such that at least a 50% chance that at least two share birthdays. This value is 23 and we will try to find out .We will try to answer this problem by getting some feeling about probability. What is the probability that all the N persons share their birthday[they all have the birthday on same day]. it is 1/365^(N-1). We will consider this for 2 persons. First person can have birthday on any of 365 days and second’s birthday also must be on the same day as first so total number of favorable cases are 365 and total number of days are 365*365. Generalizing it for 3 persons do not change the number of favorable cases [still 365] but total number of cases is 365^3 so for N persons to have birthday on the same day 365/365^N. You can see it more intuitive if you try to generate the tree of this problem.Root of the tree [ first person] will have 365 branches. Now for each branch there will be another 365 branches [second person] so total number of leaves[pairs] is 365*365. Out of these 365*365 birthday pair , only 365 pairs which have same value [(1st jan , 1st jan) , (2 jan,2jan)……………. ……………(31 dec , 31 dec)]. You can keep continue this tree for 3 , 4 persons to get the picture clear[It helped me lot].Now what does the 1-(1/365^(N-1)) represents ? The probability that None will have same birthday , two will have same birthday , …………(N-1) will have same birthday ie they all don’t have birthday on same day.

What if the problem is twisted in following manner. What is the probability that all of the N persons will have different birthday.We first try to find out answer for 2 persons.Using same counting technique , first person can have birthday on any of 365 days then second can have his birthday on remaining 364 day so the favorable cases[ none of the two will have the birthday on the same day ] are 365*364 and total number of cases are 365*365[Try to generate the tree ].The probability of no two person will have birthday on same day is 365*364/(365*365). For third person’s birthday will be remaining 363 days. Continuing this, Nth person will have birthday on remaining (365-N+1) days. So the number of favorable cases when they all [N persons] will have birthday on different days are 365*364*………..(365-N+1) and total number of cases are 365^(N). The probability that they all have different birthday is P = 365*364………(365-N+1)/365^N. Now what does 1-P represents ? All of them will have same birthday , N-1 will have same birthday ……………….2 will have same birthday ie. they all do not have different birthday[There are at least 2 person which have birthday on same day]. So probability that at least 2 will have birthday on same day is
1-(365*364……….(365-N+1))/365^N where 2<=N<=365. N=23 gives .507297

Advertisements

August 26, 2010 - Posted by | Programming

No comments yet.

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

%d bloggers like this: