Birthday Probability: CR4 Challenge (09/09/08)

I think that number is about right for the US, though the numbers are higher amongst "African Americans".

I understand that there are parts of Africa where the numbers are more than double.

So in some parts of the world there could be a significant probability that a group of 23 people includes two twins - but bear in mind that these twins would not necessarily be a pair.

I've read the ratio is also higher among those of Scandanavian descent - Swedes, Norwegians, Finns, Danes, etc.

The answer was supposed to be revealed yesterday. So is it 548 or what? Don't make me come over there!

I understand that there are parts of Africa where the numbers are more than double.

According to Wikipedia, the Yoruba tribe of West Africa has the highest twin birthrate of any ethnic group. But, what is the probability of someone conducting this duplicate birthday experiment in West Africa? Also, what is the probability of future comments in this thread using the word "probability"?

Last question:

Unity, except if they change the title

You're probably right...

What is the significance of word "AT LEAST" here. If we take the same question without these words will the answer be different?

Without "at least", you would need precisely two people sharing the same birthday. That means that situations where (for example) three people shared one birthday or there were two days on which people shared birthdays would be excluded from the count - so the number of people would be slightly larger.

As pointed out previously,

Say, if 23 is the answer, then 24, 25, 26... and so on would give

AT LEAST 2 matched birthdays, or even more, i.e. 3, 4, 5... matched birthdays,

of probability GREATER THAN 1/2.

I therefore challenge it should be the MINIMUM number of people that would give 2 matched birthdays, NOT 3, 4, 5, ... matched birthdays!

Or, any number bigger than this MINIMUM would give more matches!

Reading all inputs, I believe we all agree that, for any 2 person pair, their probability of matched birthday is 1/365, neglecting leap years. (1/365 is therefore Not an average!)

Do you still insist "23" as the correct answer? Using 23, you've included 3, 4, 5,...N matched birthdays already!

AC Wing.

You have a supporter here. I have been reading the past posts with interest.

Statement 1

When there are 20 people in the room, there is a more than 50% chance AT LEAST one match is there.

Statement2

Until 23 people enter there is a more than 50% chance that birthday of a person already in the room is not matched by the last person (or anyone who entered before) who entered the room.

i.e. When there are 23 people in the room there is a more than 50% chance "???" one match is there.

Can someone tell me an appropriate word for "???"

(May be both of us are stupid and/or stubborn)..don't sue me for calling you that!-I already have two defamation law suits against me for 22 million & 26 million- of course the currency is Sri Lankan Rupees!

"Can someone tell me an appropriate word for "???""

That

milo

Your statement 1 is incorrect. I imagine it to be based on the formula

n.(n-1)/365/2

To show that this formula cannot be correct for all cases, consider the situation when there are 28 people in the room. This formula gives the probability as 1.0356. If we allow that to mean 1, that would mean that at least two people share a birthday on every single occasion. But it is possible for 28 people to be born on different days, so that is clearly wrong.

If the formula fails at 28 people, we have no reason to suppose it is correct at 20 people, where I believe that you have used it.

If you now return to SlideRuler's post #5 with a more open mind, you should see that he is not discounting occasions on which more than two people share a birthday - what he is doing is merely to ensure that the occasions on which three people or more share a birthday are each only counted once.

If that still does not convince, I suggest you try with a hypothetical year of three days, and with three people in the room. This will allow you to write down all 27 possible different birthday arrangements, and observe that exactly 6 of these possibilities do not include coincident birthdays. This gives a probability of 7/9 that there will be at least two people with coincident birthdays.

This is the same as given by SlideRuler's formula, whereas the other formula predicts a probability of unity.
I hope that one of these is enough for you either
. to agree the number - or
. to express the basis of your disagreement in a manner that I can follow.

Fyz

Yes, complete agree with you! We are tuned.

Cheers,

AC Wing.

The question says the minimum number of people that would produce at least 2 matched birthdays. That is the minimum number that is needed to produce any of 2, 3, 4 and upwards matched birthdays. If we perform the experiment with 23 people in the room a very large number of times, on half of occasions there will be a pair of people with a matched birthday; there will be more than two people with matched birthdays on nearly a quarter of the occasions, and these event will (correctly) be included in the number.

If we demanded exactly two matched birthdays, the number would be even higher.

You statement, n.(n-1)/365/2 does not produce any answer. Fair enough, we understand what you mean and I have no intention to pinpoint any funny mistakes for purpose other than those necessary for finding out the intended answer.

Let me show my calculations later.

Let's read the original untwisted question again: which states

How many people must be in a room in order for the probability to be greater than 1/2 that at least two of them have the same birthday? (By "same birthday", we mean the same day of the year; the year may differ.) Ignore leap years.

which is of course different to Physicist's input #111:

"the minimum number of people that would produce at least 2 matched birthdays. That is the minimum number that is needed to produce any of 2, 3, 4 and upwards matched birthdays(This is a twisted part, NOT stated in the original question). If we perform the experiment with 23 people in the room a very large number of times, on half of occasions there will be a pair of people with a matched birthday; there will be more than two people with matched birthdays on nearly a quarter of the occasions, and these event will (correctly) be included in the number."

As I said before, now we all agree, that the question had open ceilings, like

1. How many people (Seems no one would argue that we have to look for the minimum of people which I pointed out previously. If not, any number bigger than the minimum would satisfy the required constraints.)

2. probability to be greater than 1/2 (then we can use 1/2 as the minimum probability, any probability bigger than that would give the answer as well, but I am NOT taking it as bigger than unity, as will explain later)

3. at least (meaning this is the lowest requirement)

4. two of them have the same birthday (if 3 and 4 are view collectively together, as they are written together, then situations with only 2 people match starts to satisfy the requirement, and the minimum number of persons that give such 1 coincidence (i.e. 2 persons with matched birthday) is the answer)

My reason to choose 20 is because this is the minimum number of people that would give probability of 1/2 of at least 2 persons have same birthday. If we argue both (2 matches and 2 or more matches)can be possible scenarios of the question, then 20 is still the minimum of the 2 possible answers, hence I stand firm on my ground, 20, as explained.

Read that again:

"at least two of them have the same birthday"

So, any number of people have 1 pair of birthday coincidence will satisfy the required constraints. Of course, any number bigger than this number, the MINIMUM, would also answer this opened ceiling question. But, as we accept the MINIMUM is what we are looking for, then 20 should be the answer. Why? Here is my calculations:

Probability of have 1 pair people with birthday coincidence = 1/365 (ignoring leap years)

Let N be the minimum number of people inside the room that satisfy the requirements, then there are totally

^NC₂ possible ways of pairing of these N people, each with probability of birthday coincidence = 1/365.

Therefore their total probability of them having birthday coincidence is:

^NC₂×1/365

and we want to limited these probability to 1/2, hence the equation:

^NC₂×1/365 = 1/2 (Surely, 1/365 is not meant to be averaging the combination with number of days of the year, although numerically it happens to be the same)

as stated by sahasushank

N=20 (round off to the next integer). This includes combinations of A and B (B and A is treated as same as A and B, and would not repeat counted), A and C, A and D...A and T, B and C, B and D, ...B and T, ...S and T. Yes, combinations of Brenda and Arthur, Arthur and whoever are included in this estimation.

Now, comes Physicists's problem; the question start from asking the number of people, and N is the number of people that is true only at the probability of just bigger than 1/2 and the equations stated clearly about that. Physicists moved to higher number (of different probability) and said then the probability was great than unity, hence the higher number (say, 28) is not true and hence 20 could not be right!

This is like finding the L where L*3=6. When we say L=2, but someone argue that L cannot be equation to 2 because if we took L as 4, the product is not 6 any longer and hence we cannot accept L=2 as the right answer!

^NC₂×1/365 = 1/2 is only true when the probability is 1/2 and we use this equation only for the situation of finding such MINIMUM number of people, NOT the probability, P_n! N so found therefore satisfies the conditions of probability of great than 1/2, having at least 2 persons of having matched birthday

When understood that 23 actually included the cases of A and B and C, A and B and D, A and C and D..., A and B and C and D and E and F(which is actually more than at least 2 have matched birthdays, number of people so found is therefore not the minimum already)... The only possible way to explain these increased number was of course to twist the question to say they are included, but they are actually NOT!

Honestly, when I read back, I found it is much better than not to say anything about people are wrong, not even telling what was wrong without name! I therefore went off to say who is right only, and I did not want to point out problems!

Actually, had I make anyone feel bad about challenging your statement or pointing out troubles, I did not mean to make you feel bad, I found most of the time, your inputs are all highly valuable and I appreciate those tried to help! It was sometimes disturbing to see stupid politics in the market, especially at work and average people do not bother to care between right or wrong, just make those who can do it right to do all the work.... That's why I took steps to try to point out what I believe to be the truth! No offence meant! When in rush, my sentences tend to be short and concise, nothing meant to be instructive!

I take part in CR4 discussions because I found this an interesting place that people are genuinely devoting to find out truth, solving even the hardest questions without compromising anything, yield no way to politics, racist and discriminations. I hope this could be preserved!

Hope that would help, and I cannot guarantee my statement is comprehensive to all readers, if most of you understand, I am happy!

Unfortunately, this was not only long, but often impenetrable. For example "different to Physisist's input #111". There were two interpretations in #111, and the one that I said corresponded to the challenge was apparently indistinguishable from your interpretation.

But, returning to the real issue:
You appear to agree that n.(n-1)/365/2 cannot be correct because it gives an answer that is obviously nonsense for n=28.
You then proceed to use ⁿC₂x1/365 as the basis for your calculations. But
ⁿC₂x1/365 can be written as n!/(n-2)!/2!x(1/365), and this is exactly the same as n.(n-1)/365/2. So you are still trying to use something that gives a nonsense answer when n=28 (check this with your calculator if you are still in doubt).

Now you hopefully recognise that the equation you are using cannot be valid, take a look at the more tractable case that I described - three people in the room and a three-day year. Then perhaps you may be ready to drop your preconceptions about what SlideRuler and MPM were doing in their calculations - and to recreate their actual processes.

Here (for what it is worth) is my attempt at a different description of the first stages:
N.B. the versions in square braces show the correspondence with SlideRuler's presentation
1 person in room:
. probability = 0 . [=1-(365/365)]
2 people in room:
. probability = 1/365 . [= 1-(365/365)*(364/365)]
3 people in room:
. probability of no previous coincidences = 364/365
. probability of coincidence if there were no previous coincidences = 2/365
. => probability of additional coincidence = (364/365).(2/365)
. Total probability of there being a coincidence =
. 1/365 + (364/365).(2/365) . [= 1 - (365/365)*(364/365)*(363/365)

I missed that you wrote:

"Now, comes Physicists's problem; the question start from asking the number of people, and N is the number of people that is true only at the probability of just bigger than 1/2 and the equations stated clearly about that. Physicists moved to higher number (of different probability) and said then the probability was great than unity, hence the higher number (say, 28) is not true and hence 20 could not be right!

This is like finding the L where L*3=6. When we say L=2, but someone argue that L cannot be equation to 2 because if we took L as 4, the product is not 6 any longer and hence we cannot accept L=2 as the right answer!"

It is not like that at all. I am not saying that the formula [Probability = function(N)] is wrong because the answer it gives for the probability at N=28 is not 1/2. I am saying that it is wrong because the formula gives an at N=28 that is simply not possible. In principle you could propose a range of validity for the formula, but to justify this range you would need to have a mechanism that could be shown to not to influence the result inside the range of validity, but that does influence the result outside it.

In this case, you have a formula that I believe we all agree is accurate for N=1 and for N=2. I think we also agree that it fails for N=28.
So the question is: where does it fail, and what is the reason. If you could find a mechanism that only appears for values of N>20 and that would cause it to fail, that would at least allow you to rationalise that it could be right at N=20. However, you have not attempted to do this, and you are unlikely to find such a mechanism.
On the other hand, a mechanism has been proposed that would cause the formula to fail at N=3. In the circumstances, I imagine you would want to examine that mechanism rather more carefully.

The quiz is an old timer and I thought I knew how to get that magical 23. Nevertheless, I admit I got almost convinced when I saw your approach^NC₂×1/365 = 1/2 which at first seemed perfectly valid. I scratched my head for some time, but now I think I can see where's the flaw:

In order to use multiplication to calculate the probability of various events occurring separately, it is necessary that they are independent. Otherwise, we need to consider conditional probabilities.

Coming to our case now, the probability that a pair is good (i.e. it gives a birthday match), depends on whether another pair is good or not, therefore not all pairs of the^NC₂ ones are independent. Imagine, for example, that we have three people, A, B and C. If it is given that neither A and B are a good pair, nor A and C, then we know that the chance that the B and C are a good pair is not 1/365 but 1/364.

It is so easy to slip when dealing with probabilities. That's why I've always hated them...

Are you saying that if there are red, green and blue balls in a bag, then matching one of the color with a 4th ball is NOT an independent event? This is well established!

Everyone has one and only one birthday, the probability of matching one pair of person is therefore always 1/365, according to the given conditions. Matching A and B is 1/365, matching A and C is the same! It is NOT linked event, not mutually exclusive... Whether A is born on Jan 1, doest not affect if B would be born in Jan 1. (As we discussed, seasonal, holiday factors that affect reception is not considered here).

Tell me if you have a better answer!

AC Wing.

When I first looked at this challenge, I thought the answer was 20, too. I enjoy this forum, and learn from it frequently, as in this case. Fyz is right, the answer is 23.

A basic definition of probability is the number of favorable outcomes / the number of total outcomes. If I understand your argument correctly, you state that combinations with more than two matching birthdays should not be included, and doing so inflates the number to 23. However, if you don't include these combinations in the calculation, then the number goes beyond 23 because there are less favorable outcomes.

I admit my understanding of this subject is, shall I say, woeful. I cannot explain why this problem is set-up to find the probability for not matching first. My guess is that the combinatorial math for this approach is much easier to determine. Indeed, what would be the math for determining the amount of combinations with only matching pairs of 2 birthdays? I set-up a small piece of VBA code an used an example of four dice. Total combinations, 6^4 or 1296. Number of combinations where all four dice are the same, 6. Number of combinations where three dice are the same, 120. Number of combinations where only 2 are the same(possible for combination to have two pair), 810. Number of combinations where there are no matches, 360. In this case, the combinatorial math would have predicted (5*4*3*2)/6^4 = 360 combinations with no matching dice, or 1296-360= 936 combinations with matching dice. I do not know the combinational math to derive the number of combinations with just pairs (2) matching dice from "n" number of dice.

I went as far as downloading a 520 page document titled "Introduction to Probability" by Charles M. Grinstead and J. Laurie Snell, and found that it had this exact problem on page 77, example 3.3. While the presentation of the math is different from what was offered as a solution here, the result was still the same, with 23 people the probability is just over 50% there is a matching birthday.

The download was free, and I found it informative. A link to it is provided at http://www.dartmouth.edu/~chance/teaching_aids/books_articles/probability_book/book.html

Once we have the probability of one or more coincident birthday pairs, the probability of a single pair is not that difficult to find – provided that you can accept a recurrence relation rather than an explicit formula (there's probably an explicit formula lurking, but I didn't find it).

Suppose with N people in room, this probability is P1(N).

Add one more person:
. If there was previously exactly one coincident birthday, this would have a 1/365 probability of becoming multiple (or 364/365 of remaining as a single event).
. If there were previously no coincident birthdays {probability =365!/(365-N)!/365^N}, the probability of creating a coincidence would be N/365

This leads to the following recurrence relation:
P1(N+1) = P1(N).364/365 + N/365.(365!/(365-N)!/365^N

Relevant probabilities are given in the table below for N=1 to 28.
You can see that for a probability greater than 0.5 we would need 24 people to be in the room

By the way, the maximum probability of there being exactly a single coincident pair peaks at N=54, with a value of ~ 0.9066687

P.S. I was in two minds whether to mark this "off topic".

I'm glad you didn't mark it OT, it would have made the GA I voted you relatively useless. I note that to the number of (what I would regard as) significant decimal places, the (number of people = 23) is essentially a 50:50 split between "no coincident" and "1 coincident" birthdays. That means that 23 should be the correct answer to the OP, and it matches the answer I remember from some 40+ years ago when I first heard the explanation of the answer to this problem.

FWIW, that explanation was short, simple, and easy to understand, but, curse the luck, impossible (for me, at least) to remember! Ah, the Mists of Time - how they DO obscure...

I'm certain the original explanation was the same as SlideRuler's, except supported by diagrams or arm-waving. Can't manage the armwaving on CR4, but different wording and some daft detail might help.

You want the probability of there being at least one coincidence, which must be the same as:
1 - (probability of zero coincidences).

For distributions that give zero coincidences with N people, (365-N) days of the year are unoccupied, so the probability of it still being zero coincidences when you add a person is (365-N)/365.
Thus, if the probability of zero coincidences for N people is P₀(N), then the probability of zero coincidences for (N+1) people is P₀(N).(365-N)/365, which gives
P₀(N) = 365/365.364/365...(365-(N-1))/365 = 365!/(365-N)!/365^N

So the probability of at least one coincidence for N people is:
P_coincident(N) = 1 - 365!/(365-N)!/365^N

N.B. although the principles in my post #120 were correct, there was a silly mistake. I've resubmitted a corrected version #123 (with check sums). You'll see that the probability never even approaches 0.5. Naturally, I've voted against the G.A.s of the original.
BTW, the challenge read "more than 1/2" - not almost exactly 1/2.

I'm not quite following you're post. Are you stating probability for just pairs, as in no matches containing more that 2 birthdays?

If you are looking at the probability of only one single matched birthday pair in a room of "n" people, may I suggest the following approach:

If a single match exists in a room of people, and one of the people exits whose birthday matches, then you now have a room with no matching birthdays, the probability of for this "n-1" group is

P(No Match, n-1) = (365 * 364 * 363 * .... (365 - n))/365^(n-1)

Now the next person entering the room has a probability of matching with this group is equal to the product of probability of no matches to the "n-1" point and the probability of matching next (which is the 1 - the probability of no matches for "n");

P(Match, n) = P(No Match, n-1) * (1 - (365 * 364 * 363 * ... (365 - n + 1))/365^n)

Running the math, I calculated that the probability max is 0.26597 at 23 people (however coincidental that may be).

Comparing these probabilities with those generated for any match, the numbers look ok, and are equal for the n=2 scenario as expected, and are never greater than the any match probabilities.

I have a table of data, but I don't know how to post it.

I can't see any basis for what you suggest.

As I said before, I'm certain that the basis of the method I presented is sound - the only question is whether I've made an elementary mistake. Anyone willing to take the trouble to follow the method should also be able to spot any careless slips.

N.B. that the method can readily be extended to larger numbers of coincident birthdays if desired.

Your explicit equation is definitely an improvement on my recurrent version, so you've found the expression that I didn't. Naturally, you get the GA vote.

But I tried my equation again - and it seemed to work. Maybe I'm entering what it should be rather than what I wrote - or maybe the problem is with the calculated number being
P1(N+1) = function{P1(N)} rather than
P1(N) = function(P1(N-1)
as it's only too easy to take the value of N from the wrong line in the way I've written it.

Thanks, Fyz. I'll take it as a compliment.

Congratulations on "keeping your cool" and objectivity with the exchanges you had with AC_Wing.

You have shown great insight into the problem and deserve a GA somewhere. I gave it here

For those who supported me, I haven't given up yet. I just did not want to bother with this kind of arguement!

The minimum size of population that gives 1 coincidence, is good enough as the number of people for at least 2 person having matched birthday at the specified probability. If 20 satisfied the conditions, of course 28 must be at higher probability and using 28 as number of different probability to argue 20 is not right, is totally unfounded.

Physicists is very good at his English. Good job that maths is nothing like you can twist. Including 2, 3, 4, ... 23 coincidences means it was an answer higher than what is expected. I noticed also, the simulation is done using the condition described by SlideRuler's, i.e. more than 1 coincidence of birthday!

There is nothing new from Physicist and SlideRuler's. Telling the same thing again and again, might lead somebody to believe you are right, but it does not change the truth though! Are there anything new so that you can shake off the incursion of extra matches that Physicist tried to twist?

I wasn't going to bother with this, let me show you one last time, when I'll be free next! Say your opinions all now so that, I don't have to repeat again and again my point of views!

AC Wing.

Explicit formula for a single pair of coincident birthdays.

Although I would have presented this in any case, perhaps the main significance is that is shows how the basis of the approach proposed by AC_WING can be extended to include the number of combinations of dates on which individual birthdays can occur – and thus to give the correct answer.

We may calculate the probability of exactly a single pair of coincident birthdays as follows:

We use Y to be the number of days in a year, and N to be the number of people in the room.
Obviously, the number of days on which there will be birthdays is (N-1). These are selected from the Y days in the year, so the number of different possibilities for the selected days is ^YC_(N-1).
The number of possible choices of coincident pairs of birthdays is ^NC₂.
The number of possible orderings of the (N-1) birthdates is (N-1)!.

Therefore, the total number of different ways in which exactly two people can share a birthday is:
^YC_(N-1). ^NC₂. (N-1)!

On the other hand, the total number of different ways that the birthdays of N people can be distributed is Y^N.

Therefore, the probability of exactly two people sharing one birthday is:
^YC_(N-1).^NC₂.(N-1)!/Y^N

I have checked results using the above formula against the results given in post #123 using the recurrence relation.
Failing mistypes in this posting (and much to my relief) they are identical.

My guess is that there would need to be 183 people in the room in order for you to have a better than 1/2 chance of having the same birthday. (1/2 365 possible dates)

I think you are trying to answer a different question: How many other people would there have to be in the room before there is a 50% chance that you have the same birthday as one of the others? But what happens if, as is likely, some of them share the same birthday? Obviously there will be fewer days on which they have birthdays, so the probability that you share a birthday with one of them will be reduced. The answer to this new question is the same as the number of people that would have to be in the room for the expected number of days on which people have birthdays to exceed 365/2. That would need significantly more than 183 people. the actual value is the value of N for which (364/365)^N becomes less than 0.5. As (1-δ)^N decays approximately exponentially with increasing N, my first estimate for this would be about 365.ln(2), or 253 - which it turns out gives the expected number of different days on which the other people have a birthday is 182.67.

Old as the hills.