wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> Birthday gathering
        
(Message started by: NickH on Oct 19th, 2002, 6:36pm)
Title: Birthday gathering
Post by NickH on Oct 19th, 2002, 6:36pm
What is the minimum number of people that must be gathered in a room for there to be at least an even chance that all 365 birthdays are represented?  Assume birthdays are randomly distributed throughout a 365 day year; i.e., ignore leap years.

Nick
Title: Re: NEW PUZZLE: Birthday gathering
Post by Jeremy on Oct 21st, 2002, 6:47am
I'm pretty sure this is the answer:


The chance of a single person having any birthday on one of the 365 days: 1/1
the chance person number 2 has a birthday on the first person's birthday : 1/365
chance person number 3 has a birthday on one of the other 2 birthdays : 3/365
etc.
1/365+2/365+3/365+4/365... +x/365 >= .5
or
(1+2+3+4... +x)/365 >= .5
or
x(x+1)/730 >= .5

what 2 consecutive numbers will be closest to 365?
19*20... so 20 people in a room will work.
Title: Re: NEW PUZZLE: Birthday gathering
Post by S. Owen on Oct 21st, 2002, 11:18am
The answer can't be less than 365. Are you answering the more usual question, which is "how many people must be in a room before there is better than an even chance that at least two have the same birthday?" The answer to that is close to what you give.

Probability that no two among n people share a birthday =
(probability that first person doesn't share a birthday with 0 others before) *
(probability that second person doesn't share a birthday with 1 others before) *
... *
(probability that nth person doesn't share a birthday with n-1 others before) =
365/365 * 364/365 * ... * (365-n+1)/365
The question is when does this become < 0.5, and it does so first at n=23.

I have an answer to the original question but I haven't thought it through so much yet... 2366.
Title: Re: NEW PUZZLE: Birthday gathering
Post by Garzahd on Oct 21st, 2002, 3:54pm
I sketched out the probability distribution for up to 4 people by hand, and man is it ugly. So, onward to the trusty VB compiler. Using the following program, I get this answer:   2287.  There may some rounding error involved, especially because we're dealing with figures like (365!)/(365^365). I'd be very interested if there's an elegant way to solve this by hand.

Dim g(365, 3000) As Double
g(1, 1) = 1
For i As Integer = 2 To 3000
  g(1, i) = g(1, i - 1) / 365.0
  For j As Integer = 2 To 365
    g(j, i) = (g(j, i - 1) * j / 365.0) + (g(j - 1, i - 1) * (366 - j) / 365.0)
  Next
  If g(365, i) >= 0.5 Then Stop
Next
Stop
Title: Re: NEW PUZZLE: Birthday gathering
Post by william wu on Oct 21st, 2002, 5:05pm
Regarding Jeremy's response, there may have been some confusion since I recently posted the Birthday Paradox in the medium section, as opposed to Birthday Gathering. Regarding an elegant way of solving this problem, we can do a standard balls and bins analysis, with 365 bins and N balls. Determine the value of N such that the probability all bins are filled is 50%.

First let's define our event space. Let E be the event that all 365 bins are filled. E can be written as the intersection of events Ei for i Î {1, 2, ... , 365}, where Ei is the event that the ith bin contains at least one ball. Now we want an equation for Pr(E) in terms of N. Then we can set Pr(E) = 0.5 and solve for N.

If all the events Ei are independent, then
     
     Pr(E) = Pr(E1) · Pr(E2) · ... · Pr(E365)
     
since the probability of the intersection of independent events is the product of the probabilities of each of the events. Then this would be a simple calculation. Since the balls are assumed to be independent and identically distributed among the bins,

     Pr(E)       = Pr(E1)365
                   = 1 - Pr(E1c)
                   = 1 - (364/365)N.
           
Reasoning: The probability that at least one ball falls into bin 1 is equivalent to 1 minus the probability of the complementary event, which is that no balls fall into bin 1. If no balls fall into bin 1, all the balls must fall in a different bin. The probability that one ball goes into a different bin is 364/365, since there are 364 other bins.)

But unfortunately the events aren't independent, and if you solve the above equation for N, you get N = 252.652 which doesn't make sense since when N < 365, Pr(E) = 0. To prove they are not independent, consider what happens if we know that E1 through E364 are all false, and N is greater than 0. Then we can say that E365 is true with probability 1, since the balls have to go somewhere. Whenever we have to compute the probability of interesection or union of many events that depend on each other in some nasty way, we can either: 1) look at a complementary event that may be easier to analyze, and/or 2) use the generalized inclusion-exclusion principle. In the following analysis I'll use a little bit of both. Here's the part about complementary events:

     Pr(E) = Pr( Ç Ei) = 1 - Pr(E1c È E2c È ... È E365c)
     
Reasoning: The probability that all bins are filled is equal to 1 minus the probability of the complementary event, which is that at least one bin is not filled. So bin 1 might not be filled, OR bin 2 might not be filled, OR maybe they are both not filled, etc. The clause of unions shown above expresses these thoughts. Also note that it is easier to think about the probability of Eic instead of Ei. The probability that no balls fall into bin i is simply 1 - (364/365)N. So we can use some parts of the naive analysis that incorrectly assumed independence of events.

All that's left is to apply the inclusion-exclusion formula to that clause of unions, set Pr(E) to 0.5, and solve for N. The cafeteria is closing soon though, so I'll let someone else do that :) You should see a summation symbol and an alternating sign term.


P.S. So how did I get those math operators? Check out the "suggestions, help, and faq" forum.
Title: Re: NEW PUZZLE: Birthday gathering
Post by Uwe Dippel on Jan 10th, 2003, 8:51am
As far as I know, this is wrong.
But: I'm sooo curious, why.
It sounds pretty much logically correct when I read the chain of arguments. And the result is pretty close to what it is supposed to be.
Can someone point out the mistake ??
Title: Re: NEW PUZZLE: Birthday gathering
Post by udippel on Jan 10th, 2003, 9:01am
Ooops, this was supposed to be further up at Jeremy's post and now I don't have the right to remove or change it. Something to be worked on here ... !
Jeremy convinced me and I want to know what is wrong in his chain !
Title: Re: NEW PUZZLE: Birthday gathering
Post by redPEPPER on Jan 10th, 2003, 1:52pm
Okay, let's see what's wrong with Jeremy's logic.


on 10/21/02 at 06:47:51, Jeremy wrote:
The chance of a single person having any birthday on one of the 365 days: 1/1
Correct.  You can note that this 1/1 will not be used in the equation below.  A first clue that there might be a problem.


Quote:
the chance person number 2 has a birthday on the first person's birthday : 1/365
Correct.


Quote:
chance person number 3 has a birthday on one of the other 2 birthdays : 3/365
etc.
Two mistakes here.  
First, Jeremy wrote 3/365 instead of 2/365 which is what I assume he means, as seen in the equations below.
Second, the probability is 2/365 only if number 2 has a different birthday than number 1.  That is, if the previous statement (1/365) doesn't happen.


Quote:
1/365+2/365+3/365+4/365... +x/365 >= .5
Well, this is where he loses us.  I don't know exactly what this equation is supposed to represent.

1/365 is the probability that the first two birthdays are concurrent.  What is 1/365 + 2/365?  It looks like it could be the probability that the first two are concurrent, or the third with one of the first two in case the first two are different.  But then it should be 1/365 + (1-1/365) * 2/365.  

It gets uglier when you add a fourth person, as the probability to have a common birthday with the three previous ones is 3/365 only if the previous ones don't have a day in common already.  The equation would be something like 1/365 + (1-1/365) * 2/365 + (1-1/365-((1-1/365) * 2/365)) * 3/365

And that's only 4 people.  Not only does this get ugly, but it calculates the probability that two people share a birthday, which is not the question.  And can be much more easily calculated by combining the probabilities where people don't share a birthday instead of the probabilities they do, as S. Owen showed.
Title: Re: NEW PUZZLE: Birthday gathering
Post by kenny on Jan 14th, 2003, 7:55am
Here's an approximation, using "the law of big numbers."

First, if you have N people, then the expected number who have birthdays on Jan 1 is "mu" = N/365.  The probability that none of them has a birthday on Jan. 1 is e^(-mu).  Thus, the probability that at least one has a birthday that day is 1 - e^(-mu).  This comes from the Poisson distribution, which is an approximation, but it's a very good approximation.

I then assume assume that the probability that at least one person has a birthday on Jan. 2 is independent of the probability that at least one person has a birthday on Jan. 1.  This assumption is patently false, but when the number of people becomes large, it becomes a good approximation.

We then see that the probability that all 365 possible dates are hit is
(1 - e^(-mu))^365.  We want that  to be greater or equal to 1/2.  A bit of math (and more approximation) shows that mu >= ln(365 / ln(2)) which is 6.266.  Thus, the number of people N = mu * 365 = 2287, which is the same number that Garzahd got!

This approach works because the number of dates is fairly large.   If we tried the same for "one person born in each month", it wouldn't be very accurate.  If we tried for "one person born in each hour of each day", it would be even more accurate.

-- Ken


Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board