Author |
Topic: Generalized Birthday "Paradox" (M) (Read 15026 times) |
|
william wu
wu::riddles Administrator
Gender: 
Posts: 1291
|
 |
Generalized Birthday "Paradox" (M)
« on: Sep 25th, 2003, 12:44pm » |
 Quote  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:
Posts: 4863
|
|
Re: Generalized Birthday "Paradox" (M)
« Reply #1 on: Sep 29th, 2003, 6:28pm » |
Quote 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
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: Generalized Birthday "Paradox" (M)
« Reply #3 on: Sep 30th, 2003, 2:18am » |
Quote 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.
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Generalized Birthday "Paradox" (M)
« Reply #5 on: Sep 30th, 2003, 7:04pm » |
Quote 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. 
|
|
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:
Posts: 4489
|
|
Re: Generalized Birthday "Paradox" (M)
« Reply #6 on: Sep 30th, 2003, 10:07pm » |
Quote 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%.
(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
Gender:
Posts: 1291
|
|
Re: Generalized Birthday "Paradox" (M)
« Reply #7 on: Sep 30th, 2003, 11:44pm » |
Quote 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%.
(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:
Posts: 4863
|
|
Re: Generalized Birthday "Paradox" (M)
« Reply #8 on: Oct 2nd, 2003, 5:17pm » |
Quote 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. 
|
|
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:
Posts: 3
|
|
Re: Generalized Birthday "Paradox" (M)
« Reply #9 on: Nov 14th, 2003, 5:36am » |
Quote 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
 
Gender:
Posts: 727
|
|
Re: Generalized Birthday "Paradox" (M)
« Reply #10 on: Nov 14th, 2003, 6:15am » |
Quote 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:
Posts: 4489
|
|
Re: Generalized Birthday "Paradox" (M)
« Reply #11 on: Nov 14th, 2003, 8:31am » |
Quote Modify
|
on Sep 30th, 2003, 9:14am, william wu wrote:
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 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
|
|
Re: Generalized Birthday "Paradox" (M)
« Reply #13 on: Dec 13th, 2003, 5:28am » |
Quote Modify
 Remove
|
FYI, found this :
http://www.mathcad.com/library/LibraryContent/puzzles/soln28/soln28.html
|
|
IP Logged |
|
|
|
Lil' bopeep
Guest
|
 |
Re: Generalized Birthday "Paradox" (M)
« Reply #14 on: Apr 28th, 2004, 3:47am » |
Quote Modify
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:
Posts: 13730
|
|
Re: Generalized Birthday "Paradox" (M)
« Reply #15 on: Apr 28th, 2004, 3:53am » |
Quote 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
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: Generalized Birthday "Paradox" (M)
« Reply #18 on: Mar 14th, 2005, 8:47am » |
Quote Modify
|
on Mar 14th, 2005, 5:34am, Kishor wrote:
But what is the question? 
|
|
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:
Posts: 4863
|
|
Re: Generalized Birthday "Paradox" (M)
« Reply #19 on: Mar 14th, 2005, 7:50pm » |
Quote 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
|
|
Re: Generalized Birthday "Paradox" (M)
« Reply #20 on: May 7th, 2005, 11:45pm » |
Quote Modify
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:
Posts: 13730
|
|
Re: Generalized Birthday "Paradox" (M)
« Reply #21 on: May 8th, 2005, 2:43pm » |
Quote 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:
Posts: 10
|
|
Re: Generalized Birthday "Paradox" (M)
« Reply #22 on: Nov 6th, 2006, 11:02am » |
Quote 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 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.
Gender:
Posts: 1672
|
|
Re: Generalized Birthday "Paradox" (M)
« Reply #24 on: Dec 9th, 2006, 8:37am » |
Quote Modify
|
What site did you find that solution on? Maybe I'll explore it for some inspiration.
|
| « 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
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print