wu :: forums - Print Page


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

        riddles >> hard >> Generalized Birthday "Paradox" (M)
        
(Message started by: william wu on Sep 25^th, 2003, 12:44pm)

Title: Generalized Birthday "Paradox" (M)
Post by william wu on Sep 25^th, 2003, 12:44pm

~~How many people would you need in a room such that k of them have even odds of having the same birthday? (Same birthday in this context means the same month and day, but not the same year.)~~

How many people would you need in a room such that there is a 50% chance that at least k of them have the same birthday? (Same birthday in this context means the same month and day, but not the same year.)

What is the minimum number of people you would need in a room such that there is at least a 50% chance that at least k of them have the same birthday? (Same birthday in this context means the same month and day, but not the same year.)

Note 1: Wording revised 9:43 PM 9/29/2003 and 9:12 AM 9/30/2003 and 11:43 PM 9/30/2003

Note 2: 2:40 AM 10/29/2003 Unless you know of a certain obscure technique (relatively very new and not taught in most probability classes) for solving this problem, I wouldn't bother trying. It's too hard and you'll spend like a year on it.

Title: Re: Generalized Birthday "Paradox" (M)
Post by Icarus on Sep 29^th, 2003, 6:28pm

I'm not entirely sure what it is you are asking for. Do you mean that it is even odds that there will be a group of k people with the same birthday?

Title: Re: Generalized Birthday "Paradox" (M)
Post by william wu on Sep 29^th, 2003, 9:44pm

Yes. Wording revised in first post now.

Title: Re: Generalized Birthday "Paradox" (M)
Post by THUDandBLUNDER on Sep 30^th, 2003, 2:18am

I think Icarus' point was 'Do you mean exactly k or at least k?'

Title: Re: Generalized Birthday "Paradox" (M)
Post by william wu on Sep 30^th, 2003, 9:14am

At least k

Title: Re: Generalized Birthday "Paradox" (M)
Post by Icarus on Sep 30^th, 2003, 7:04pm

on 09/30/03 at 02:18:55, THUDandBLUNDER wrote:

I think Icarus' point was 'Do you mean exactly k or at least k?'

My question was exactly the one William answered. But the other one is helpful too, so at least it wasn't wasted. ;)

Title: Re: Generalized Birthday "Paradox" (M)
Post by THUDandBLUNDER on Sep 30^th, 2003, 10:07pm

Quote:

My question was exactly the one William answered.

In that case, William's question should read "...such that there is at least a 50% chance that...".
Because of the numbers involved, the chance will never be exactly 50%. ;) ;)

(Or perhaps he does mean exactly 50%?)

Title: Re: Generalized Birthday "Paradox" (M)
Post by william wu on Sep 30^th, 2003, 11:44pm

on 09/30/03 at 22:07:13, THUDandBLUNDER wrote:

wording revised again to preclude the possibility that your answer will have fractional people

Title: Re: Generalized Birthday "Paradox" (M)
Post by Icarus on Oct 2^nd, 2003, 5:17pm

on 09/30/03 at 23:44:40, william wu wrote:

wording revised again to preclude the possibility that your answer will have fractional people

*Sigh* I guess that means my half-brother has lost another job. :(

Title: Re: Generalized Birthday "Paradox" (M)
Post by Tom_Horton on Nov 14^th, 2003, 5:36am

I've done the calculations before and the answer was fairly suprising. [hide] Rather than looking for the probability of it occuring find the probability of it NOT occuring. An easier concept to envision.

Someone has put a solution on the web at: "www2.shore.net/~karr/java/Birthday.html"

It includes an peice of code to solve various similar situations. I've not included "the answer" so not to spoil the puzzle. [/hide]

Title: Re: Generalized Birthday "Paradox" (M)
Post by wowbagger on Nov 14^th, 2003, 6:15am

on 11/14/03 at 05:36:44, Tom_Horton wrote:

I've not included "the answer" so not to spoil the puzzle.

That's the reason why it is common practice around here to hide (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_suggestions;action=display;num=1043138466) solutions. You can find more info on that in the corresponding thread in the FAQ section (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_suggestions;action=display;num=1043138466).

Title: Re: Generalized Birthday "Paradox" (M)
Post by THUDandBLUNDER on Nov 14^th, 2003, 8:31am

on 09/30/03 at 09:14:05, william wu wrote:

At least k

Perhaps it would better to start with the easier problem of 'exactly k' and then to take it from there.

Title: Re: Generalized Birthday "Paradox" (M)
Post by SWF on Nov 17^th, 2003, 6:09pm

If r days are chosen at random from a list of s allowed days, the probability of a particular day being chosen h times is r!/h!/(r-h)!*(s-1)^r-h/s^r. To make this equation more useful below, I define the following function
p(h,r,s). This function is taken as 1/s^r if r=h, otherwise if s=1 or h>r the function is 0, otherwise
p(h,r,s)=r!/h!/(r-h)!*(s-1)^r-h/s^r.

Next, find the probability that every day of the year has less than k birthdays assigned to it. Take the year to have N possible birthdays, and there are Q people in the room. Each date may therefore have anywhere from 0 to k-1 birthdays matched to it. The probability that the first date of the year has m₁ birthdays matched with it is p(m₁,Q,N). That leaves Q-m₁ birthdays to distribute among N-1 possible dates. The probability that the second date of the year has m₂ birthdays matched with it is therefore p(m₂,Q-m₁,N-1). And so on for all N dates of the year. The product of these gives probability of exactly m₁, m₂,...m_N birthdays assigned to each date. Sum over each allowable m_j from 0 to k-1 gives the probability that every day has less than k birthdays assigned to it:

http://www.ai.rug.nl/~towr/PHP/FORMULA/formula.php?id=68

Solve for the smallest Q that makes this less than or equal to 0.50 and there is your answer.

Although correct, this expression is very inefficient for large N. Fortunately, the question does not require that the solution be efficient, and William would never so cruel as to rephrase this question for a fifth time after all my hard work.

Title: Re: Generalized Birthday "Paradox" (M)
Post by Margit on Dec 13^th, 2003, 5:28am

FYI, found this :
[hide]http://www.mathcad.com/library/LibraryContent/puzzles/soln28/soln28.html[/hide]

Title: Re: Generalized Birthday "Paradox" (M)
Post by Lil' bopeep on Apr 28^th, 2004, 3:47am

The problem is actually very simple. So knowing that there are 365 possibilities (ignoring february 29th and such), we can start with the following:
Given a starting birthday. The probability that a second birthday is unique is 364/365. The probability that subsequent birthdays are unique is (365 - n)/365. Multiplying these out we get the probability that a set of n birthdays is unique as (364!)/((365^n)*(364-n)!) This can be expanded to see when it reaches a probability just below 50% I only have a scientific calculator so this took some time. But other than that is very simple.

Title: Re: Generalized Birthday "Paradox" (M)
Post by towr on Apr 28^th, 2004, 3:53am

That only solves the problem for k=2 if I'm not mistaken, and not the general problem for any k.

Title: Re: Generalized Birthday "Paradox" (M)
Post by Secret_mind on Jan 2^nd, 2005, 5:56pm

http://www.mathcad.com/library/LibraryContent/puzzles/soln28/soln28.html

Title: Re: Generalized Birthday "Paradox" (M)
Post by Kishor on Mar 14^th, 2005, 5:34am

It's 23. U can see the answer in the following link.

http://www.geocities.com/bleongcw/probability.ps

Kishor

Title: Re: Generalized Birthday "Paradox" (M)
Post by THUDandBLUNDER on Mar 14^th, 2005, 8:47am

on 03/14/05 at 05:34:18, Kishor wrote:

It's 23.

But what is the question? ::)

Title: Re: Generalized Birthday "Paradox" (M)
Post by Icarus on Mar 14^th, 2005, 7:50pm

In case, T&B's reply is too cryptic, Kishor, there is a reason William called this the generalized birthday paradox.

The question is: how many people are required for there to be at least 50% probability that at least k of them have the same birthday.

The number 23 is the answer for k=2, but not other values of k.

Title: Re: Generalized Birthday "Paradox" (M)
Post by Akhil Pal on May 7^th, 2005, 11:45pm

I have to do a Science Research Project on "The Birthday Paradox." All I've found so far is that the answer is 23. You need a minimum of 23 random people for there to be a 50:50 chance that 2 people will have the same birthday. I've also tried looking for books, but the have very little information. If you guys can tell me some more on the "Birthday Paradox," please let me know. Just send it to my email address...
akhilmj23@yahoo.com

Thanks!

Title: Re: Generalized Birthday "Paradox" (M)
Post by towr on May 8^th, 2005, 2:43pm

I'm not sure what more you'd want to know than what is written in this thread, and the sites linked and mentioned here.
Also this is about the generalization of the birthday paradox, so 23 is not the answer. It is just the answer for a specific case.

Title: Re: Generalized Birthday "Paradox" (M)
Post by indiauec on Nov 6^th, 2006, 11:02am

following is possible solution
[hideb]
if n be the minimum number of people then sample space( total number of possible solutions)
S = 365^n
now number of combinations where there is no more then (k-1 ) birth days in any single day is
number of solutionm to equation
x1 + x2 + x3 + .......+x365 = n
0<x1,x2,x3,....,x365 <k-1 ,
coefficient of x^n in
[1 + x + x^2 + x^3+.......+x^(k-1)] ^ 365
that is coefficient of x^n in
(1-x^k)^365 * (1-x)^(-365)
say is is m then using binomial theorem
(verify it I have forgotten binomial coeff )
m = (364+n)C(n-1) - 365 * (364+n-k)C(k)
now just find n such that
m/S < .5
[/hideb]

Title: Re: Generalized Birthday "Paradox" (M)
Post by grungy on Dec 9^th, 2006, 2:59am

[hide]OK. I'll modify this slightly... say you are in a line. You can join the line whenever you want - nobody can take your spot once you decide you want it. To be the first person who shares a birthday, you should try and be the 20th person in line.[/hide]

And for those who want the huge mathematical explanation...

[hide]Suppose you are the Kth person in line. Then you win if and only if the K-1 people ahead all have distinct birthdays AND your birthday matches one of theirs. Let
A = event that your birthday matches one of the K-1 people ahead
B = event that those K-1 people all have different birthdays
Then
Prob(you win) = Prob(B) * Prob(A | B)

(Prob(A | B) is the conditional probability of A given that B occurred.)

Now let P(K) be the probability that the K-th person in line wins, Q(K) the probability that the first K people all have distinct birthdays (which occurs exactly when none of them wins). Then

P(1) + P(2) + ... + P(K-1) + P(K) = 1 - Q(K)
P(1) + P(2) + ... + P(K-1) = 1 - Q(K-1)

P(K) = Q(K-1) - Q(K) <--- this is what we want to maximize.

Now if the first K-1 all have distinct birthdays, then assuming uniform distribution of birthdays among D days of the year, the K-th person has K-1 chances out of D to match, and D-K+1 chances not to match (which would produce K distinct birthdays). So
Q(K) = Q(K-1)*(D-K+1)/D = Q(K-1) - Q(K-1)*(K-1)/D
Q(K-1) - Q(K) = Q(K-1)*(K-1)/D = Q(K)*(K-1)/(D-K+1)

Now we want to maximize P(K), which means we need the greatest K such that P(K) - P(K-1) > 0. (Actually, as just given, this only guarantees a local maximum, but in fact if we investigate a bit farther we'll find that P(K) has only one maximum.) For convenience in calculation let's set K = I + 1. Then
Q(I-1) - Q(I) = Q(I)*(I-1)/(D-I+1)
Q(I) - Q(I+1) = Q(I)*I/D

P(K) - P(K-1) = P(I+1) - P(I)
= (Q(I) - Q(I+1)) - (Q(K-2) - Q(K-1))
= Q(I)*(I/D - (I-1)/(D-I+1))

To find out where this is last positive (and next goes negative), solve
x/D - (x-1)/(D-x+1) = 0

Multiply by D*(D+1-x) both sides:
(D+1-x)*x - D*(x-1) = 0
Dx + x - x^2 - Dx + D = 0
x^2 - x - D = 0

x = (1 +/- sqrt(1 - 4*(-D)))/2 ... take the positive square root
= 0.5 + sqrt(D + 0.25)

Setting D=365 (finally deciding how many days in a year!),
desired I = x = 0.5 + sqrt(365.25) = 19.612 (approx).

The last integer I for which the new probability is greater than the old is therefore I=19, and so K = I+1 = 20.

Computing your chances of actually winning is slightly harder, unless you do it numerically by computer. The recursions you need have already been given.[/hide]

Title: Re: Generalized Birthday "Paradox" (M)
Post by Whiskey Tango Foxtrot on Dec 9^th, 2006, 8:37am

What site did you find that solution on? Maybe I'll explore it for some inspiration. ;)

Title: Re: Generalized Birthday "Paradox" (M)
Post by THUDandBLUNDER on Dec 9^th, 2006, 10:28am

on 12/09/06 at 08:37:15, Whiskey Tango Foxtrot wrote:

What site did you find that solution on? Maybe I'll explore it for some inspiration. ;)

Please feel free: http://brainyplanet.com/index.php/Line%20Solution?PHPSESSID=98133811aa8397f93ceb0a8893bb7775

::)

Title: Re: Generalized Birthday "Paradox" (M)
Post by Whiskey Tango Foxtrot on Dec 9^th, 2006, 10:56am

Brainy planet, eh? Thanks.

Title: Re: Generalized Birthday "Paradox" (M)
Post by THUDandBLUNDER on Dec 10^th, 2006, 4:17am

on 12/09/06 at 10:56:58, Whiskey Tango Foxtrot wrote:

Brainy planet, eh? Thanks.

Give a cheeky monkey a typewriter and....

Title: Re: Generalized Birthday "Paradox" (M)
Post by Locke64 on Jan 6^th, 2007, 10:56am

I've heard this one before. [hide]You have to work backwards (find the chances that they don't have the same birthday).[/hide]
I'm working on it now. (I forgot how to do it. >_<)

Title: Re: Generalized Birthday "Paradox" (M)
Post by Locke64 on Jan 6^th, 2007, 11:26am

on 01/06/07 at 10:56:23, Locke64 wrote:

I've heard this one before. [hide]You have to work backwards (find the chances that they don't have the same birthday).[/hide]
I'm working on it now. (I forgot how to do it. >_<)

The number of people required for there to be at least a 50% chance of two of them sharing the same birthday is [hide]23[/hide].

In order to solve it, you must [hide]first find the probability of people not sharing the same birthday as anyone else. For one person, it's 365/365 (We're ignoring leap years BTW), since it is impossible to share a birthday with anyone else because there is no one else to share a birthday with.
If you add a second person, the probability would be 364/365, since he could have a birthday on any day but the first person. The third person would have a probability of 363/365, since he must not share a birthday with either of the first two. Obviously, the numerator decreases by one each time a person is added. With this knowledge, you can make a table, multiplying 365/365x364/365x363/365...:[/hide]

IGNORE THE TABLE IF YOU WANT TO DO IT ON YOUR OWN!!!
(you can't put tables in hides.) :(
15

people	1	2	3	4	5	6	7	8	9	10	11	12	13	14	16	17	18	19	20	21	22	23
probablity	.997	.991	.984	.973	.96	.944	.926	.905	.883	.859	.833	.806	.777	.747	.716	.685	.653	.621	.589	.556	.524	.493

[hide]After you found the number of people needed to bring the probability of no two of them sharing the same birthday down below 50, just subtract it from one to find the probability of two people sharing the same birthday. ;)[/hide]

Title: Re: Generalized Birthday "Paradox" (M)
Post by Locke64 on Jan 6^th, 2007, 11:39am

nvm, I misunderstood the question. I'm not mathematically advanced enough to solve that one. :(

Title: Re: Generalized Birthday "Paradox" (M)
Post by hiyathere on Jan 6^th, 2007, 2:51pm

Personally, I think I have an easier answer, unless someone already posted it. I'm not completely sure about this, though.

[hide]365/2=182.5, so I would say 183+k number of people.[/hide]

Title: Re: Generalized Birthday "Paradox" (M)
Post by Locke64 on Jan 6^th, 2007, 3:03pm

on 01/06/07 at 14:51:46, hiyathere wrote:

Personally, I think I have an easier answer, unless someone already posted it. I'm not completely sure about this, though.

[hide]365/2=182.5, so I would say 183+k number of people.[/hide]

Trust me, that's wrong. ;)
It is known that the answer for 2 people is [hide]23[/hide]. [hide]183+2 is not equal to 23.[/hide]

Title: Re: Generalized Birthday "Paradox" (M)
Post by hiyathere on Jan 6^th, 2007, 5:16pm

on 01/06/07 at 15:03:42, Locke64 wrote:

Trust me, that's wrong. ;)
It is known that the answer for 2 people is [hide]23[/hide]. [hide]183+2 is not equal to 23.[/hide]

What do you mean? How do you know that?

Title: Re: Generalized Birthday "Paradox" (M)
Post by Locke64 on Jan 6^th, 2007, 5:23pm

on 01/06/07 at 17:16:54, hiyathere wrote:

What do you mean? How do you know that?

Well, if you go through the steps in my previous post, you'll find out for yourself, plus most other people here could explain it even better than me, and there are many websites that you can find that have that as the correct answer. But that's just for 2, not for k.

Title: Re: Generalized Birthday "Paradox" (M)
Post by Whiskey Tango Foxtrot on Jan 6^th, 2007, 9:54pm

I just noticed T 'n' B called me a cheeky monkey a month ago! How rude!

At least I got a typewriter though. ;D

Title: Re: Generalized Birthday "Paradox" (M)
Post by THUDandBLUNDER on Jan 7^th, 2007, 5:10am

on 01/06/07 at 21:54:48, Whiskey Tango Foxtrot wrote:

I just noticed T 'n' B called me a cheeky monkey a month ago!

Er...no, I implied that grungy was a cheeky monkey.

Title: Re: Generalized Birthday "Paradox" (M)
Post by Locke64 on Jan 7^th, 2007, 9:37am

To find the number of people needed so that the probability of 3 people having the same birthday is at least 50%, would you do 365/365*365/365*364/365*363/365*362/365...?

Title: Re: Generalized Birthday "Paradox" (M)
Post by Whiskey Tango Foxtrot on Jan 7^th, 2007, 9:45am

on 01/07/07 at 05:10:38, THUDandBLUNDER wrote:

Er...no, I implied that grungy was a cheeky monkey.

:-[ :D

Title: Re: Generalized Birthday "Paradox" (M)
Post by THUDandBLUNDER on Jan 7^th, 2007, 11:43am

on 01/07/07 at 09:37:11, Locke64 wrote:

To find the number of people needed so that the probability of 3 people having the same birthday is at least 50%, would you do 365/365*365/365*364/365*363/365*362/365...?

Exactly 3 or at least 3?

Title: Re: Generalized Birthday "Paradox" (M)
Post by Locke64 on Jan 7^th, 2007, 11:49am

on 01/07/07 at 11:43:27, THUDandBLUNDER wrote:

Exactly 3 or at least 3?

Well, to find how many people you need for 2 ppl to have the same birthday, you use [hide]365/365*364/365...[/hide], so If I add one to the requirement, I'd think I'd have to add one more impossible ([hide]365/365[/hide]) to the list of factors.

Title: Re: Generalized Birthday "Paradox" (M)
Post by Locke64 on Jan 7^th, 2007, 12:14pm

on 01/07/07 at 11:49:08, Locke64 wrote:

Actually, that can't be right. All that would be doing is adding one person, since it is multiplying it by one and not changing any of the rest of the calculation.

Title: Re: Generalized Birthday "Paradox" (M)
Post by StallionMang on Jan 5^th, 2008, 9:58pm

OK. I think I've got it.

In the original "birthday" problem, we found the probability that no two people have the same birthday, and then took the complement of that fraction to obtain the probability that at least two have the same birthday.

Now let's set k to the value of 4, for example.

So in order to obtain the probability that at least 4 people have the same birthday, let's take the probability that we derived in the original riddle - the probability that at least 2 people have the same birthday: (365^n) - (365!/((365-n)!(365^n)))

We simply take this probability and subtract from it the probabilities that EXACTLY three people have the same birthday and that EXACTLY two people have the same birthday.

The probability that EXACTLY three people have the same birthday is:

(n!/(3!(n-3)!))*365 / 365^n

and two people:

(n!/(2!(n-2)!))*365 / 365^n

(Probability of At Least Two) - (Probability of EXACTLY 3 )- (Probability of EXACTLY 2) = Probability of At Least 4.

So in order to scale this up for all values of k, we simply say that for any value of k greater than 2, just take Probability of At Least Two and subtract from it the sum of all probabilities that EXACTLY p number of people have the same birthday for all values of p where p>1 and p<k.

Did I get it right?

Title: Re: Generalized Birthday "Paradox" (M)
Post by ThudanBlunder on Jan 5^th, 2008, 11:30pm

StallionMang, I think you fail to take into account the fact that more than one pair/trio/etc can share different birthdays.

Probability(3 or More) http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/ne.gif 1 - Probability(None) - Probability(1 Pair)

Probability(3 or More) = 1 - Probability(None) - Probability(1 Pair) - Probability(2 Pairs Share 2 Different Birthdays) - ... - Probability(n/2 Pairs Share n/2 Different Birthdays)

Title: Re: Generalized Birthday "Paradox" (M)
Post by StallionMang on Jan 6^th, 2008, 12:53am

Alas, you are right.

And on top of that, my equations for calcuating the number of possible combinations for EXACTLY 3 and EXACTLY 2 people with the same birthday were completely wrong. I was doing C(n,3) * 365, which is not right.

Oh well....back to the drawing board.

Thanks!

Title: Re: Generalized Birthday "Paradox" (M)
Post by skeptic1000 on May 1^st, 2008, 10:43am

Has anyone already tried finding the answer for the first several values of k, and then attempted to detect some sort of pattern that might make the answer more apparent?