Posts Tagged ‘Birthday Paradox’

Birthday Paradox

Posted by guptaradhesh on November 26, 2010

Something amazing paradoxical given by probability which is hard to accept in real life.

I had to sit and analyze the proof to accept this:

“In a room of just 23 people there’s a 50-50 chance of two people having the same birthday. In a room of 57 there’s a 99% chance of two people matching.”

Here is the explaination:  (reference: http://mathworld.wolfram.com/)

Consider the probability Q_1(n,d) that no two people out of a group of n will have matching birthdays out of d equally possible birthdays. Start with an arbitrary person’s birthday, then note that the probability that the second person’s birthday is different is (d-1)/d, that the third person’s birthday is different from the first two is [(d-1)/d][(d-2)/d], and so on, up through the nth person. Explicitly,

Q_1(n,d) = (d-1)/d(d-2)/d...(d-(n-1))/d
=  ((d-1)(d-2)...[d-(n-1)])/(d^(n-1)).

so the probability P_2(n,d) that two or more people out of a group of n do have the same birthday is therefore

P_2(n,d) = 1-Q_1(n,d)
= 1-(d!)/((d-n)!d^n).

If 365-day years have been assumed, the number of people needed for there to be at least a 50% chance that at least two share birthdays is the smallest n such that P_2(n,365)>=1/2. This is given by n=23, since

P_2(23,365) = (38093904702297390785243708291056390518886454060947061)/(75091883268515350125426207425223147563269805908203125)
 approx 0.507297.

Hence the astounding Birthday Paradox..

Posted in puzzles/ algorithms | Tagged: , , | Leave a Comment »