Question on the Birthday Problem

**Danny09** · November 28th 2011, 06:33 PM

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!

**Danny09** · November 29th 2011, 10:31 AM

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.

**takatok** · November 30th 2011, 12:23 AM

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):
$P(n,k) = \frac{n!}{(n-k)!}$

so your equation is

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

$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 $\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:
$P(None) = (\frac{11}{12})^{\frac{k*(k-1)}{2}}=.5$

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

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

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

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

$k^2-k = 15.932$

Then using quadratic method you can solve:

$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)

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

So 1-.419 = 58.1%.

The actual probablity with 5 people is:
$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.

**Danny09** · November 30th 2011, 03:37 PM

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):
$P(n,k) = \frac{n!}{(n-k)!}$

so your equation is

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

$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 $\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:
$P(None) = (\frac{11}{12})^{\frac{k*(k-1)}{2}}=.5$

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

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

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

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

$k^2-k = 15.932$

Then using quadratic method you can solve:

$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)

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

So 1-.419 = 58.1%.

The actual probablity with 5 people is:
$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!

Thread: Question on the Birthday Problem

LinkBack

Thread Tools

Display

Question on the Birthday Problem

Re: Question on the Birthday Problem

Re: Question on the Birthday Problem

Re: Question on the Birthday Problem

Similar Math Help Forum Discussions

birthday problem

Birthday Problem

Probability question, The birthday problem

Birthday question

The Birthday Problem (another probability question)

Search Tags