Question on the Birthday Problem

Hello all! I had a quick question on the (in)famous birthday problem,

The question itself reads :

*Assuming that people are equally likely to be born in each of the twelve months, how many people must be gathered to guarantee a probability of at least 0.5 that two of them have birthdays in the same month?*

I know the formula for solving the problem is 1 - P(12,k)/12^k <--- k=number of people

However I have no idea how so solve for P(12,k), silly I know.

Anyways, would someone mind pointing me in the right direction, it would be greatly appreciated! Thanks in advance!

Re: Question on the Birthday Problem

Quote:

Originally Posted by

**Danny09** Hello all! I had a quick question on the (in)famous birthday problem,

The question itself reads :

*Assuming that people are equally likely to be born in each of the twelve months, how many people must be gathered to guarantee a probability of at least 0.5 that two of them have birthdays in the same month?*

I know the formula for solving the problem is 1 - P(12,k)/12^k <--- k=number of people

However I have no idea how so solve for P(12,k), silly I know.

Anyways, would someone mind pointing me in the right direction, it would be greatly appreciated! Thanks in advance!

Apologies for the double post, but since this question has to be answered within the hour,

I'm getting desperate.

Is solving for P(A,B) as simple as division?

Probability of event A / Prob. Of B.

Re: Question on the Birthday Problem

Well I realize its probably too late for your deadline but here you go:

P(12,k) is a permutation (Note: its a different than a combination):

$\displaystyle P(n,k) = \frac{n!}{(n-k)!}$

so your equation is

$\displaystyle 1 - \frac{\frac{12!}{(12-k)!}}{12^k} >= 0.5$

$\displaystyle 12^k- \frac{12!}{(12-k)!}>=12^k*0.5$

This is gonna be a pain to solve for and one method is to just plug in values of k, starting at 2 and going on up. You don't have to try that many since, 13 people are guaranteed to have the same birthday.

There are a lot of ways to approximate this ,and the easiest is this:

There are $\displaystyle \frac{k*(k-1)}{2}$ ways we can pair everyone up. If we assume each pair is independent of each other, we can find the probability that all the pairs don't have the same month for a birthday.

The odds of any pair not having the same birthday is 11/12, and the probability that None of them have the same birthday is:

$\displaystyle P(None) = (\frac{11}{12})^{\frac{k*(k-1)}{2}}=.5$

This is a little easier to solve: Take the $\displaystyle log_{\frac{11}{12}}$ of both sides:

$\displaystyle \frac{k*(k-1)}{2} = log_{\frac{11}{12}}0.5$

Now convert the right side to $\displaystyle log_{10}$

$\displaystyle \frac{k*(k-1)}{2} = \frac{log_{10} 0.5}{log_{10}\frac{11}{12}}$

$\displaystyle k^2-k = 15.932$

Then using quadratic method you can solve:

$\displaystyle k^2-k-15.932=0$

Note this will come out to roughly k=4.5. So we know we need 5 people.

If you plug in 5 people (10 combinations = 5*4/2)

$\displaystyle (\frac{11}{12})^{10} = .419 $

So 1-.419 = 58.1%.

The actual probablity with 5 people is:

$\displaystyle 1-\frac{\frac{12!}{(12-5)!}}{12^5} = 61.8% $

I believe this is because the approximate method isn't counting all the times when more than 2 people have the same month birthday. But its a pretty low % difference. As long as k is not near an integer ( e.g k=4.4) you can be pretty safe in assuming your actual k you need is k rounded up, in this case 5. But if is very a near an integer.. say k=4.01 or k=4.98 you might need to check both number near k.. in the first case k =4 and k=5.. In the second case k =5 and 6.

Re: Question on the Birthday Problem

Quote:

Originally Posted by

**takatok** Well I realize its probably too late for your deadline but here you go:

P(12,k) is a permutation (Note: its a different than a combination):

$\displaystyle P(n,k) = \frac{n!}{(n-k)!}$

so your equation is

$\displaystyle 1 - \frac{\frac{12!}{(12-k)!}}{12^k} >= 0.5$

$\displaystyle 12^k- \frac{12!}{(12-k)!}>=12^k*0.5$

This is gonna be a pain to solve for and one method is to just plug in values of k, starting at 2 and going on up. You don't have to try that many since, 13 people are guaranteed to have the same birthday.

There are a lot of ways to approximate this ,and the easiest is this:

There are $\displaystyle \frac{k*(k-1)}{2}$ ways we can pair everyone up. If we assume each pair is independent of each other, we can find the probability that all the pairs don't have the same month for a birthday.

The odds of any pair not having the same birthday is 11/12, and the probability that None of them have the same birthday is:

$\displaystyle P(None) = (\frac{11}{12})^{\frac{k*(k-1)}{2}}=.5$

This is a little easier to solve: Take the $\displaystyle log_{\frac{11}{12}}$ of both sides:

$\displaystyle \frac{k*(k+1)}{2} = log_{\frac{11}{12}}0.5$

Now convert the right side to $\displaystyle log_{10}$

$\displaystyle \frac{k*(k+1)}{2} = \frac{log_{10} 0.5}{log_{10}\frac{11}{12}}$

$\displaystyle k^2-k = 15.932$

Then using quadratic method you can solve:

$\displaystyle k^2-k-15.932=0$

Note this will come out to roughly k=4.5. So we know we need 5 people.

If you plug in 5 people (10 combinations = 5*4/2)

$\displaystyle (\frac{11}{12})^{10} = .419 $

So 1-.419 = 58.1%.

The actual probablity with 5 people is:

$\displaystyle 1-\frac{\frac{12!}{(12-5)!}}{12^5} = 61.8% $

I believe this is because the approximate method isn't counting all the times when more than 2 people have the same month birthday. But its a pretty low % difference. As long as k is not near an integer ( e.g k=4.4) you can be pretty safe in assuming your actual k you need is k rounded up, in this case 5. But if is very a near an integer.. say k=4.01 or k=4.98 you might need to check both number near k.. in the first case k =4 and k=5.. In the second case k =5 and 6.

Thanks very much! You explained the point I was stuck at and went even further explaining a method not even my professor discussed! I'm actually using the same technique on other similar problems right now, it's quite helpful!

Appreciate it!