wu :: forums
wu :: forums - Generalized Birthday "Paradox" (M)

Welcome, Guest. Please Login or Register.
Sep 25th, 2018, 12:22pm

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   hard
(Moderators: ThudnBlunder, Grimbal, william wu, SMQ, towr, Eigenray, Icarus)
   Generalized Birthday "Paradox" (M)
« Previous topic | Next topic »
Pages: 1 2  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: Generalized Birthday "Paradox" (M)  (Read 13934 times)
william wu
wu::riddles Administrator
*****





   
WWW

Gender: male
Posts: 1291
Generalized Birthday "Paradox" (M)  
« on: Sep 25th, 2003, 12:44pm »
Quote Quote Modify Modify

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.
« Last Edit: Oct 29th, 2003, 2:42am by william wu » IP Logged


[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
Icarus
wu::riddles Moderator
Uberpuzzler
*****



Boldly going where even angels fear to tread.

   


Gender: male
Posts: 4863
Re: Generalized Birthday "Paradox" (M)  
« Reply #1 on: Sep 29th, 2003, 6:28pm »
Quote Quote Modify Modify

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?
« Last Edit: Sep 29th, 2003, 6:30pm by Icarus » IP Logged

"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
william wu
wu::riddles Administrator
*****





   
WWW

Gender: male
Posts: 1291
Re: Generalized Birthday "Paradox" (M)  
« Reply #2 on: Sep 29th, 2003, 9:44pm »
Quote Quote Modify Modify

Yes. Wording revised in first post now.
IP Logged


[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
*****




The dewdrop slides into the shining Sea

   


Gender: male
Posts: 4489
Re: Generalized Birthday "Paradox" (M)  
« Reply #3 on: Sep 30th, 2003, 2:18am »
Quote Quote Modify Modify

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

THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
william wu
wu::riddles Administrator
*****





   
WWW

Gender: male
Posts: 1291
Re: Generalized Birthday "Paradox" (M)  
« Reply #4 on: Sep 30th, 2003, 9:14am »
Quote Quote Modify Modify

At least k
IP Logged


[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
Icarus
wu::riddles Moderator
Uberpuzzler
*****



Boldly going where even angels fear to tread.

   


Gender: male
Posts: 4863
Re: Generalized Birthday "Paradox" (M)  
« Reply #5 on: Sep 30th, 2003, 7:04pm »
Quote Quote Modify Modify

on Sep 30th, 2003, 2:18am, 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. Wink
IP Logged

"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
*****




The dewdrop slides into the shining Sea

   


Gender: male
Posts: 4489
Re: Generalized Birthday "Paradox" (M)  
« Reply #6 on: Sep 30th, 2003, 10:07pm »
Quote Quote Modify Modify

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%. Wink  Wink
 
(Or perhaps he does mean exactly 50%?)  
 
« Last Edit: Nov 14th, 2003, 6:17am by ThudnBlunder » IP Logged

THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
william wu
wu::riddles Administrator
*****





   
WWW

Gender: male
Posts: 1291
Re: Generalized Birthday "Paradox" (M)  
« Reply #7 on: Sep 30th, 2003, 11:44pm »
Quote Quote Modify Modify

on Sep 30th, 2003, 10:07pm, THUDandBLUNDER wrote:

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%. Wink Wink
 
(Or perhaps he does mean exactly 50%?)
 

 
wording revised again to preclude the possibility that your answer will have fractional people
« Last Edit: Oct 1st, 2003, 8:28am by william wu » IP Logged


[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
Icarus
wu::riddles Moderator
Uberpuzzler
*****



Boldly going where even angels fear to tread.

   


Gender: male
Posts: 4863
Re: Generalized Birthday "Paradox" (M)  
« Reply #8 on: Oct 2nd, 2003, 5:17pm »
Quote Quote Modify Modify

on Sep 30th, 2003, 11:44pm, 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.  Sad
IP Logged

"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
Tom_Horton
Newbie
*





   


Gender: male
Posts: 3
Re: Generalized Birthday "Paradox" (M)  
« Reply #9 on: Nov 14th, 2003, 5:36am »
Quote Quote Modify Modify

I've done the calculations before and the answer was fairly suprising.   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.

 
« Last Edit: Nov 15th, 2003, 7:42am by Tom_Horton » IP Logged
wowbagger
Uberpuzzler
*****





242002184 242002184    


Gender: male
Posts: 727
Re: Generalized Birthday "Paradox" (M)  
« Reply #10 on: Nov 14th, 2003, 6:15am »
Quote Quote Modify Modify

on Nov 14th, 2003, 5:36am, 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 solutions. You can find more info on that in the corresponding thread in the FAQ section.
« Last Edit: Nov 14th, 2003, 6:16am by wowbagger » IP Logged

"You're a jerk, <your surname>!"
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
*****




The dewdrop slides into the shining Sea

   


Gender: male
Posts: 4489
Re: Generalized Birthday "Paradox" (M)  
« Reply #11 on: Nov 14th, 2003, 8:31am »
Quote Quote Modify Modify

on Sep 30th, 2003, 9:14am, 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.
IP Logged

THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
SWF
Uberpuzzler
*****





   


Posts: 879
Re: Generalized Birthday "Paradox" (M)  
« Reply #12 on: Nov 17th, 2003, 6:09pm »
Quote Quote Modify Modify

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/sr.  To make this equation more useful below, I define the following function
p(h,r,s).  This function is taken as 1/sr 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/sr.
 
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 m1 birthdays matched with it is p(m1,Q,N).  That leaves Q-m1 birthdays to distribute among N-1 possible dates.  The probability that the second date of the year has m2 birthdays matched with it is therefore p(m2,Q-m1,N-1). And so on for all N dates of the year. The product of these gives probability of exactly m1, m2,...mN birthdays assigned to each date.  Sum over each allowable mj from 0 to k-1 gives the probability that every day has less than k birthdays assigned to it:
 

 
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.
IP Logged
Margit
Guest

Email

Re: Generalized Birthday "Paradox" (M)  
« Reply #13 on: Dec 13th, 2003, 5:28am »
Quote Quote Modify Modify Remove Remove

FYI, found this :
http://www.mathcad.com/library/LibraryContent/puzzles/soln28/soln28.html
IP Logged
Lil' bopeep
Guest

Email

Re: Generalized Birthday "Paradox" (M)  
« Reply #14 on: Apr 28th, 2004, 3:47am »
Quote Quote Modify Modify Remove Remove

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.
IP Logged
towr
wu::riddles Moderator
Uberpuzzler
*****



Some people are average, some are just mean.

   


Gender: male
Posts: 13640
Re: Generalized Birthday "Paradox" (M)  
« Reply #15 on: Apr 28th, 2004, 3:53am »
Quote Quote Modify Modify

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

Wikipedia, Google, Mathworld, Integer sequence DB
Secret_mind
Guest

Email

Re: Generalized Birthday "Paradox" (M)  
« Reply #16 on: Jan 2nd, 2005, 5:56pm »
Quote Quote Modify Modify Remove Remove

http://www.mathcad.com/library/LibraryContent/puzzles/soln28/soln28.html
IP Logged
Kishor
Newbie
*





   


Posts: 1
Re: Generalized Birthday "Paradox" (M)  
« Reply #17 on: Mar 14th, 2005, 5:34am »
Quote Quote Modify Modify

It's 23. U can see the answer in the following link.
 
http://www.geocities.com/bleongcw/probability.ps
 
Kishor
IP Logged
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
*****




The dewdrop slides into the shining Sea

   


Gender: male
Posts: 4489
Re: Generalized Birthday "Paradox" (M)  
« Reply #18 on: Mar 14th, 2005, 8:47am »
Quote Quote Modify Modify

on Mar 14th, 2005, 5:34am, Kishor wrote:
It's 23.  

But what is the question?   Roll Eyes
 
IP Logged

THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
Icarus
wu::riddles Moderator
Uberpuzzler
*****



Boldly going where even angels fear to tread.

   


Gender: male
Posts: 4863
Re: Generalized Birthday "Paradox" (M)  
« Reply #19 on: Mar 14th, 2005, 7:50pm »
Quote Quote Modify Modify

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.
« Last Edit: Mar 14th, 2005, 7:51pm by Icarus » IP Logged

"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
Akhil Pal
Guest

Email

Re: Generalized Birthday "Paradox" (M)  
« Reply #20 on: May 7th, 2005, 11:45pm »
Quote Quote Modify Modify Remove Remove

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!
IP Logged
towr
wu::riddles Moderator
Uberpuzzler
*****



Some people are average, some are just mean.

   


Gender: male
Posts: 13640
Re: Generalized Birthday "Paradox" (M)  
« Reply #21 on: May 8th, 2005, 2:43pm »
Quote Quote Modify Modify

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.
IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
indiauec
Newbie
*



vaibhav

   


Gender: male
Posts: 10
Re: Generalized Birthday "Paradox" (M)  
« Reply #22 on: Nov 6th, 2006, 11:02am »
Quote Quote Modify Modify

following is possible solution  
hidden:

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
IP Logged
grungy
Newbie
*





   


Posts: 20
Re: Generalized Birthday "Paradox" (M)  
« Reply #23 on: Dec 9th, 2006, 2:59am »
Quote Quote Modify Modify

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.
 
And for those who want the huge mathematical explanation...
 
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.
IP Logged
Whiskey Tango Foxtrot
Uberpuzzler
*****



Sorry Goose, it's time to buzz a tower.

   
Email

Gender: male
Posts: 1667
Re: Generalized Birthday "Paradox" (M)  
« Reply #24 on: Dec 9th, 2006, 8:37am »
Quote Quote Modify Modify

What site did you find that solution on?  Maybe I'll explore it for some inspiration.  Wink
« Last Edit: Dec 9th, 2006, 8:37am by Whiskey Tango Foxtrot » IP Logged

"I do not feel obliged to believe that the same God who has endowed us with sense, reason, and intellect has intended us to forgo their use." - Galileo Galilei
Pages: 1 2  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

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