[Guest]

Hi, smart guys,

I am teased by a math probability question, could anyone help to figure it out.

The problem is

Assue there is 365 days each year, there is n people in a room. What is the probability that at least k people have the same birth day? Assume n < 365, k > 2.

Edited May 21, 2011 by Solow

[Aaryan]

Unless I am mistaken, there is an almost 100% chance (or close to) of at least two people having the same birthday.

Obviously, if n>365, at least two people have the same birthday, or a 100%.

However, if n<365, everyone has a 1 in 365 chance of their birthday (i.e. Bob has a 1/365 chance of being born on Jan 1.)

In order to find the probability of everyone to have a different birthday, you must use exponents or 1/365ⁿ. Using this, the answer will become smaller and smaller, very close to zero. That is the probability of everyone having a DIFFERENT birthday, meaning very close to 100% chance of at least two people having the same birthday. 100% * almost 100%= something close to 100%.

Bu don't take my word for it. Let some of the more Senior Members take a look at it.

[Aaryan]

Edit: double post

Edited May 21, 2011 by Aaryan

[Akriti]

Well, I saw this in "million 2 one". I agree with Aaryan coz it was proved in the show, practically.

[Guest]

I think the BD paradox is relevant here. K and N need to be known in order to solve the probability. The BD paradox states that if 23 people are in one room, there is a 50% chance that two people will have the same B-day. It all depends on the variables. Although it seems weird, if you conduct the BD paradox experiment, you'll be surprised.

[Aaryan]

Edit: I realized now that n<365 and k>2 , so completely discard the part about n being greater than 365.

[Guest]

I think the BD paradox is relevant here. K and N need to be known in order to solve the probability. The BD paradox states that if 23 people are in one room, there is a 50% chance that two people will have the same B-day. It all depends on the variables. Although it seems weird, if you conduct the BD paradox experiment, you'll be surprised.

You are right, this problem is variant of Birthday Paradox.

But here k > 2.

To simplify, assume k = 3.

How did you solve it?

[Guest]

Unless I am mistaken, there is an almost 100% chance (or close to) of at least two people having the same birthday.

Obviously, if n>365, at least two people have the same birthday, or a 100%.

However, if n<365, everyone has a 1 in 365 chance of their birthday (i.e. Bob has a 1/365 chance of being born on Jan 1.)

In order to find the probability of everyone to have a different birthday, you must use exponents or 1/365ⁿ. Using this, the answer will become smaller and smaller, very close to zero. That is the probability of everyone having a DIFFERENT birthday, meaning very close to 100% chance of at least two people having the same birthday. 100% * almost 100%= something close to 100%.

Bu don't take my word for it. Let some of the more Senior Members take a look at it.

Thanks for your reply.

But this is probability is as least 2 people have same birth day, not k people

[Aaryan]

same thing. It was implied in the explaination. It doesnt change anything.

[Guest]

Assume k>=2

The odds that there WON'T be a 2nd birthday in the room are

for n=2, p=364/365

for n=3, p=364/365*363/365

for n=4, p=364/365*363/365*362/365

etc.

The odds of multiple birthdays are 1 minus the above results

Hi, smart guys,

I am teased by a math probability question, could anyone help to figure it out.

The problem is

Assue there is 365 days each year, there is n people in a room. What is the probability that at least k people have the same birth day? Assume n < 365, k > 2.

Edited May 21, 2011 by Simon Legree

[Guest]

The probability is 1:25 That 2 people will share a birthday.

[Guest]

Here's my answer, anyone see any faults?

Specific Case: k=3, n=100

Let: x,y, and z be people and b_x, b_y, and b_z be their birthdays.

for a given person x,

P(b_y=b_x AND b_z=b_x) = P(b_y=b_x given b_z=b_x)*P(b_z=b_x) = P(b_y=b_x)*P(b_z=b_x) (the last equality assumes the birthdays are independent).

P(b_y=b_x)=(1/365). (Given person x's birthday there is a 1/365 chance that person y has the same birthday)

and P(b_y=b_x)*P(b_z=b_x)=(1/365)(1/365) = (1/365)^2

Now, if there are 99 people other than person x, there are 99c2 (99 choose 2) combinations of y's and j's we can pick to compare with person x's birthday. For each combination, there is a (1/365)^2 chance that they are all have the same birthday.

So.. (99c2)*(1/365)^2=0.0364 or about 3.64% chance.

General Case: probability of k people having the same birthday in a room of n people = (n-1)choose(k-1) * (1/365)^(k-1)

[Guest]

[Guest]

Assume k>=2

The odds that there WON'T be a 2nd birthday in the room are

for n=2, p=364/365

for n=3, p=364/365*363/365

for n=4, p=364/365*363/365*362/365

etc.

The odds of multiple birthdays are 1 minus the above results

[Guest]

Divide the term by Factorial (n) to take care of permutation of the members amonngst themselves.

probability that no 2 members will share a birthday is

For n=2, (1/Factorial (2))*(365/365)*(364/365)

For n=3, (1/Factorial (3))*(365/365)*(364/365)*(363/365)

For n=4, (1/Factorial (4))*(365/365)*(364/365)*(363/365)*(362/365)

...

[Aaryan]

Simon pretty much summarized it well.

my explanation was using probability of AT LEAST two people having the same birthday. The odds of more people is even greater.

Basically there is a lot of multiplying fractions involved, so much that most calulators round to 100%

[Guest]

First take case of K= 2 (this has already been posted before):

What is the chance that out of N people in a Room AT LEAST 2 people will have same birthday

Let us choose Person 1 out of the N, with a birthday on a give date

Now for person 2 : what is the chance he will have a different birthday 364/365

For person 3: what is the chance he will have a different birthday than 1 & 2 363/365

For person N : what is the chance he will have a different B'day than all other (N-1) people (365-N+1)/365

For all persons 2 to N to have each a diff B'Day P = FACT(364) / FACT (365-N)/ 365^(N-1)

Prob for at least 2 to share B'day = 1 - {FACT(364) / FACT (365-N)/ 365^(N-1)}

Work out the probs like above for increasing N but K =2:

N Probability Prob of ALL Prob of atleast

of Nth person 1 to N having TWO having same

having a diff diff B'Days B'Day

B'Day

from others

2 99.7260% 99.7260% 0.2740%

3 99.4521% 99.1796% 0.8204%

4 99.1781% 98.3644% 1.6356%

5 98.9041% 97.2864% 2.7136%

6 98.6301% 95.9538% 4.0462%

7 98.3562% 94.3764% 5.6236%

8 98.0822% 92.5665% 7.4335%

9 97.8082% 90.5376% 9.4624%

10 97.5342% 88.3052% 11.6948%

.

.

23 93.9726% 49.2703% 50.7297%

24 93.6986% 46.1656% 53.8344%

25 93.4247% 43.1300% 56.8700%

26 93.1507% 40.1759% 59.8241%

27 92.8767% 37.3141% 62.6859%

28 92.6027% 34.5539% 65.4461%

29 92.3288% 31.9031% 68.0969%

30 92.0548% 29.3684% 70.6316%

So for N= 30 and K = 2 result is 70.63%

Lets go for N= 30 and K = 3

Out of the 30 above where at least 2 have same B'Day- take out one of the 2. leaving 29. Now the problem becomes find the prob of 2 having same b'day out of 29.

so teh answer would be P[n=30, k=2] x P {n=29, k=2) = 70.63 x 68.09 = 48.10% .... and likewise.

[Guest]

Combinations of N dates of 365

We have 365^N combinations of them, that include combinations, permutations and repetitions (Sorry because I don't know the math english terms exactly). In order to discard those that don't repeat any day, we calculate them: 365!/(365-N)! and substract: 365^N - 365!/(365-N)! We have the number of cases with at least two days rpeated with a sample of size N.

The next is to determine the cases with at least k repetitions with N. I think it would be combinations the N days taken k of them, plus the combinations of N taken k+1... to k=N, that will be 1 more, and all multiplied by N or 365 (Im not sure), because each day can be repeated in these positions combined.

If correct, then number of cases with k or more repetitions divided by the 365^N will be the probability.

Im going to calculate the similar problem taken the days of the week and a few people, that can be compared with and analitic calculus to prove my solution.

[Guest]

Exactly what do you mean by at K>2, is this that say 3 people must have the same specific day, or tha if 2 people have the same day, and another 2 people have the same on another day, and 2 more people have the same for another day, that this is considered 6 people that have the same birthday.

[EventHorizon]

Here's my answer, anyone see any faults?

Specific Case: k=3, n=100

Let: x,y, and z be people and b_x, b_y, and b_z be their birthdays.

for a given person x,

P(b_y=b_x AND b_z=b_x) = P(b_y=b_x given b_z=b_x)*P(b_z=b_x) = P(b_y=b_x)*P(b_z=b_x) (the last equality assumes the birthdays are independent).

P(b_y=b_x)=(1/365). (Given person x's birthday there is a 1/365 chance that person y has the same birthday)

and P(b_y=b_x)*P(b_z=b_x)=(1/365)(1/365) = (1/365)^2

Now, if there are 99 people other than person x, there are 99c2 (99 choose 2) combinations of y's and j's we can pick to compare with person x's birthday. For each combination, there is a (1/365)^2 chance that they are all have the same birthday.

So.. (99c2)*(1/365)^2=0.0364 or about 3.64% chance.

General Case: probability of k people having the same birthday in a room of n people = (n-1)choose(k-1) * (1/365)^(k-1)

for k=2 your general solution gives (n-1)choose(1) * (1/365)^1 = (n-1)/365.

Testing this with n=23 should result in over 50%.

(23-1)/365 = 22/365 ~= .0603.

Plugging in k = 2 and n = 23 like we did for the previous solution gives...

(23-0)*(1/365) = 23/365 ~= .06301

Like Jalegre alludes to... it won't be that simple. (or if it can be, I'd love to see how this mess simplifies!)

First I'll describe partitions. They are simply a way to split up a group of objects. For instance, if you had 5 pennies and wanted to split the pile into two groups, you could split them into a group of 4 and a single one or a group of three and a group of two.

I'll reference the partition function, P(n), but instead of simply the total, I will assume it is the actual set of all possible partitions.

I'll assume the partition is in the form of a multiset. For instance, let A be the partition of 8 objects as 3,2,2,1. I'll assume A_e = [3,2,1], and A_m = [1,2,1]. So I've turned the partition into two ordered lists (elements and multiplicities). This will make the math a little easier to write.

Given a single partition, The number of possible ways that can come up when categorizing n objects into x groups (x will be 365 for this original problem) is the following (where 'total' is the sum of the multiplicities (equivalent to the cardinality of the multiset), PI is the capitol pi that is the product of each element (as opposed to the capitol sigma that is commonly used for the sum of the elements)):

F(A) = n!x!/( (PI_i=1^total (A_m! * (A_e!)^A_m)) * (x-total)! )

For an example of why the pieces of the equation are there, I'll use the partition I gave above as an example (3,2,2,1 or with multiplicities as [3,2,1],[1,2,1]):

First, choose 3 of the 8 => probability so far = 8 choose 3 = 8!/(3!5!)

Choose a day for the group to be assigned => probability so far = 8!/(3!5!) * x (since they can go anywhere at the moment)

Now choose the first group of two from the remaining 5 => 8!/(3!5!) * x * (5 chooose 2) = 8!5!/(3!5!2!3!) * x = 8!/(3!2!3!) * x

Choose a day for the group to be assigned of the x-1 remaining ones => 8!/(3!2!3!) * x * (x-1)

Choose two from the remaining 3 => 8!/(3!2!3!) * x * (x-1) * (3 choose 2) = 8!/(3!2!3!) * x * (x-1) * 3!/(2!1!) = 8!3!/(3!2!3!2!1!)*x*(x-1) = 8!/(3!2!2!1!) * x * (x-1)

Wait! There are two groups of two, so you can get the same configuration two different ways! So divide by the factorial of the multiplicity => 8!/(3!2!2!1!) * x * (x-1) / 2! = 8!/(3!2!2!1! * 2!) * x * (x-1)

Choose a spot for the second group of 2 from the remaining x-2 days => 8!/(3!2!2!1! * 2!) * x * (x-1) * (x-2)

Choose 1 from the remaining 1 (does nothing in this case, but want to be consistent) => 8!/(3!2!2!1! * 2!) * x * (x-1) * (x-2) * (1 choose 1) = 8!/(3!2!2!1! * 2!) * x * (x-1) * (x-2) * 1!/(1!0!) = 8!/(3!2!2!1! * 2!) * x * (x-1) * (x-2)

Now choose a place for that 1 from the remaining (x-3) days => 8!/(3!2!2!1! * 2!) * x * (x-1) * (x-2) * (x-3)

For consistency I'll add in the factorials of the multiplicities of 1 => 8!/(3!2!2!1! * 1!2!1!) * x * (x-1) * (x-2) * (x-3)

Simplify the x's => 8!/(3!2!2!1! * 1!2!1!) * x!/(x-4)!

The 8! is n!, and the x! is over there on the right.

The factorials of the elements 3!2!2!1! could be rewritten ((3!)¹)((2!)²)((1!)¹)

The factorials of the multiplicities are there 1!2!1!

The (x-total)! is (x-4)! since there are 4 total elements in the multiset (3, 2, 2, and 1)

Yeah, so there it is.

Now for how to use this to find a probability.

You take the total number of possibilities (xⁿ) and subtract out the function of the partitions you don't want (ones with the largest element being less than 3 for k=3 in the problem). Then divide by xⁿ to get the probability (again, x is the number of categories, which in this case is 365 for the days in a year).

For n=8 and k=3, you would want to subtract out F([2,2,2,2]), F([2,2,2,1,1]), F([2,2,1,1,1,1]), F([2,1,1,1,1,1,1]), and F([1,1,1,1,1,1,1,1]).

For n=8 and k=4 the partitions are the following (copied from wikipedia so the formatting is different):

3 + 3 + 2

3 + 3 + 1 + 1

3 + 2 + 2 + 1

3 + 2 + 1 + 1 + 1

3 + 1 + 1 + 1 + 1 + 1

2 + 2 + 2 + 2

2 + 2 + 2 + 1 + 1

2 + 2 + 1 + 1 + 1 + 1

2 + 1 + 1 + 1 + 1 + 1 + 1

1 + 1 + 1 + 1 + 1 + 1 + 1 + 1

Notice that F([1,1,1,1,1,1,1,1]), aka [1] with multiplicities [8], is the case where they are all different, which is what you subtract in the case of k=2 (and is simply x!/(x-n)! once you plug in the numbers)

[Guest]

for k=2 your general solution gives (n-1)choose(1) * (1/365)^1 = (n-1)/365.

Testing this with n=23 should result in over 50%.

(23-1)/365 = 22/365 ~= .0603.

Plugging in k = 2 and n = 23 like we did for the previous solution gives...

(23-0)*(1/365) = 23/365 ~= .06301

Like Jalegre alludes to... it won't be that simple. (or if it can be, I'd love to see how this mess simplifies!)

First I'll describe partitions. They are simply a way to split up a group of objects. For instance, if you had 5 pennies and wanted to split the pile into two groups, you could split them into a group of 4 and a single one or a group of three and a group of two.

I'll reference the partition function, P(n), but instead of simply the total, I will assume it is the actual set of all possible partitions.

I'll assume the partition is in the form of a multiset. For instance, let A be the partition of 8 objects as 3,2,2,1. I'll assume A_e = [3,2,1], and A_m = [1,2,1]. So I've turned the partition into two ordered lists (elements and multiplicities). This will make the math a little easier to write.

Given a single partition, The number of possible ways that can come up when categorizing n objects into x groups (x will be 365 for this original problem) is the following (where 'total' is the sum of the multiplicities (equivalent to the cardinality of the multiset), PI is the capitol pi that is the product of each element (as opposed to the capitol sigma that is commonly used for the sum of the elements)):

F(A) = n!x!/( (PI_i=1^total (A_m! * (A_e!)^A_m)) * (x-total)! )

For an example of why the pieces of the equation are there, I'll use the partition I gave above as an example (3,2,2,1 or with multiplicities as [3,2,1],[1,2,1]):

First, choose 3 of the 8 => probability so far = 8 choose 3 = 8!/(3!5!)

Choose a day for the group to be assigned => probability so far = 8!/(3!5!) * x (since they can go anywhere at the moment)

Now choose the first group of two from the remaining 5 => 8!/(3!5!) * x * (5 chooose 2) = 8!5!/(3!5!2!3!) * x = 8!/(3!2!3!) * x

Choose a day for the group to be assigned of the x-1 remaining ones => 8!/(3!2!3!) * x * (x-1)

Choose two from the remaining 3 => 8!/(3!2!3!) * x * (x-1) * (3 choose 2) = 8!/(3!2!3!) * x * (x-1) * 3!/(2!1!) = 8!3!/(3!2!3!2!1!)*x*(x-1) = 8!/(3!2!2!1!) * x * (x-1)

Wait! There are two groups of two, so you can get the same configuration two different ways! So divide by the factorial of the multiplicity => 8!/(3!2!2!1!) * x * (x-1) / 2! = 8!/(3!2!2!1! * 2!) * x * (x-1)

Choose a spot for the second group of 2 from the remaining x-2 days => 8!/(3!2!2!1! * 2!) * x * (x-1) * (x-2)

Choose 1 from the remaining 1 (does nothing in this case, but want to be consistent) => 8!/(3!2!2!1! * 2!) * x * (x-1) * (x-2) * (1 choose 1) = 8!/(3!2!2!1! * 2!) * x * (x-1) * (x-2) * 1!/(1!0!) = 8!/(3!2!2!1! * 2!) * x * (x-1) * (x-2)

Now choose a place for that 1 from the remaining (x-3) days => 8!/(3!2!2!1! * 2!) * x * (x-1) * (x-2) * (x-3)

For consistency I'll add in the factorials of the multiplicities of 1 => 8!/(3!2!2!1! * 1!2!1!) * x * (x-1) * (x-2) * (x-3)

Simplify the x's => 8!/(3!2!2!1! * 1!2!1!) * x!/(x-4)!

The 8! is n!, and the x! is over there on the right.

The factorials of the elements 3!2!2!1! could be rewritten ((3!)¹)((2!)²)((1!)¹)

The factorials of the multiplicities are there 1!2!1!

The (x-total)! is (x-4)! since there are 4 total elements in the multiset (3, 2, 2, and 1)

Yeah, so there it is.

Now for how to use this to find a probability.

You take the total number of possibilities (xⁿ) and subtract out the function of the partitions you don't want (ones with the largest element being less than 3 for k=3 in the problem). Then divide by xⁿ to get the probability (again, x is the number of categories, which in this case is 365 for the days in a year).

For n=8 and k=3, you would want to subtract out F([2,2,2,2]), F([2,2,2,1,1]), F([2,2,1,1,1,1]), F([2,1,1,1,1,1,1]), and F([1,1,1,1,1,1,1,1]).

For n=8 and k=4 the partitions are the following (copied from wikipedia so the formatting is different):

3 + 3 + 2

3 + 3 + 1 + 1

3 + 2 + 2 + 1

3 + 2 + 1 + 1 + 1

3 + 1 + 1 + 1 + 1 + 1

2 + 2 + 2 + 2

2 + 2 + 2 + 1 + 1

2 + 2 + 1 + 1 + 1 + 1

2 + 1 + 1 + 1 + 1 + 1 + 1

1 + 1 + 1 + 1 + 1 + 1 + 1 + 1

Notice that F([1,1,1,1,1,1,1,1]), aka [1] with multiplicities [8], is the case where they are all different, which is what you subtract in the case of k=2 (and is simply x!/(x-n)! once you plug in the numbers)

[Guest]

You assume (n choose 2) pairs independent.

Here's my answer, anyone see any faults?

Specific Case: k=3, n=100

Let: x,y, and z be people and b_x, b_y, and b_z be their birthdays.

for a given person x,

P(b_y=b_x AND b_z=b_x) = P(b_y=b_x given b_z=b_x)*P(b_z=b_x) = P(b_y=b_x)*P(b_z=b_x) (the last equality assumes the birthdays are independent).

P(b_y=b_x)=(1/365). (Given person x's birthday there is a 1/365 chance that person y has the same birthday)

and P(b_y=b_x)*P(b_z=b_x)=(1/365)(1/365) = (1/365)^2

Now, if there are 99 people other than person x, there are 99c2 (99 choose 2) combinations of y's and j's we can pick to compare with person x's birthday. For each combination, there is a (1/365)^2 chance that they are all have the same birthday.

So.. (99c2)*(1/365)^2=0.0364 or about 3.64% chance.

General Case: probability of k people having the same birthday in a room of n people = (n-1)choose(k-1) * (1/365)^(k-1)