Competition - post a photo you've taken of nature >>

Birthday Problem - Maths

Hi, I am a bit confused about the maths behind the birthday problem... Just in case it is not obvious the problem is:
What is the minimum number of guests that need to be present at a party so that there is a more than 50% chance that two of them have the same birthday? Note that they do not necessarily have to be the same age, they just must have the same birthday. We can assume that a year consists of 365 days and that the probability of birth is equal for each day.

My thoughts were, what is the chance that a pair, have different b-days and 364/365 is that chance. I then looked at how many pair could be formed with N amount of people. it increase from 0,0 , 1 ,3, 6, 10 ,15.... and so on. Excluding the first term I noted that these are triangle numbers, which take the form N(N-1)/2 where N is number of people.
I therefore assumed (wrongly I think) that (364/365)^(N(N-1)/2) is the probability that we would have no matches, why is this wrong and more importantly where is the error in my thinking?

Many thanks (sorry for the long post!)

Reply 1

mqb2766

Wiki is your friend
https://en.m.wikipedia.org/wiki/Birthday_problem

Reply 2

tande33

Original post by mqb2766

Wiki is your friend
https://en.m.wikipedia.org/wiki/Birthday_problem

So is my version an approximation... What presumption have I therefore made? I am still a little confused but thanks!

Reply 3

tande33

Original post by tande33

So is my version an approximation... What presumption have I therefore made? I am still a little confused but thanks!

Oh ok I have just read that it assumes the events are independant, but surely this approximation is made for all models?

Reply 4

mqb2766

Original post by tande33

Oh ok I have just read that it assumes the events are independant, but surely this approximation is made for all model

364/365 would be the probability of a pair having different birthdays, but then your pairing argument would breakdown. You could write it as a conditional tree to see how it compares when you add another pair of you wished.

Reply 5

ghostwalker

Original post by tande33

So is my version an approximation... What presumption have I therefore made? I am still a little confused but thanks!

Interestingly, your version isn't too far out. For N=42, it's only ~10% off the true value.

Your problem, as you noted in your subsequent posting, is independence or lack thereof.

If we look at a simpler case of N=3, and use the notation for events of "AB" to represent A and B do not have the same birthday, then:

For every one to have different birthdays, we are looking at P(AB and AC and BC), which you have as (364/365)^3

If these events were independent you would be correct. Indeed, any pair of events, AB and AC, or AB and BC, or AC and BC are independent - known as pairwise independent.

However the three events taken together are not independent.

You're looking for P(AB and AC and BC) and by conditional probability this equals P(BC | (AB and AC) x P(AB and AC)

Now P(AB and AC) = (364/365)^2 ---------------- No problem there.

What about P(BC | (AB and AC))?

We know B,C are distinct from A, but we don't know B and C are distinct. Since they're distinct from A, there are only 364 choices left for each. If we choose a birthday for B, then for BC to be true, there are 363 options.

So, P(BC | (AB and AC)) = 363/364.

And when you multiply up, you get (364/365) x (363/365)

For you to be able to multiply up as you did you need the events to be mutually independent, and that is not the case here.