Author 
Topic: Generalized Birthday "Paradox" (M) (Read 13862 times) 

william wu
wu::riddles Administrator
Gender:
Posts: 1291


Generalized Birthday "Paradox" (M)
« on: Sep 25^{th}, 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 29^{th}, 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 29^{th}, 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 29^{th}, 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 30^{th}, 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 30^{th}, 2003, 7:04pm » 
Quote Modify

on Sep 30^{th}, 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 30^{th}, 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 14^{th}, 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 30^{th}, 2003, 11:44pm » 
Quote Modify

on Sep 30^{th}, 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 1^{st}, 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 2^{nd}, 2003, 5:17pm » 
Quote Modify

on Sep 30^{th}, 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 halfbrother 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 14^{th}, 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 15^{th}, 2003, 7:42am by Tom_Horton » 
IP Logged 



wowbagger
Uberpuzzler
Gender:
Posts: 727


Re: Generalized Birthday "Paradox" (M)
« Reply #10 on: Nov 14^{th}, 2003, 6:15am » 
Quote Modify

on Nov 14^{th}, 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 14^{th}, 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 14^{th}, 2003, 8:31am » 
Quote Modify

on Sep 30^{th}, 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 17^{th}, 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!/(rh)!*(s1)^{rh}/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!/(rh)!*(s1)^{rh}/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 k1 birthdays matched to it. The probability that the first date of the year has m_{1} birthdays matched with it is p(m_{1},Q,N). That leaves Qm_{1} birthdays to distribute among N1 possible dates. The probability that the second date of the year has m_{2} birthdays matched with it is therefore p(m_{2},Qm_{1},N1). And so on for all N dates of the year. The product of these gives probability of exactly m_{1}, m_{2},...m_{N} birthdays assigned to each date. Sum over each allowable m_{j} from 0 to k1 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 13^{th}, 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 28^{th}, 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)*(364n)!) 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: 13596


Re: Generalized Birthday "Paradox" (M)
« Reply #15 on: Apr 28^{th}, 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 14^{th}, 2005, 8:47am » 
Quote Modify

on Mar 14^{th}, 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 14^{th}, 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 14^{th}, 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 7^{th}, 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: 13596


Re: Generalized Birthday "Paradox" (M)
« Reply #21 on: May 8^{th}, 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 6^{th}, 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 (k1 ) birth days in any single day is number of solutionm to equation x1 + x2 + x3 + .......+x365 = n 0<x1,x2,x3,....,x365 <k1 , coefficient of x^n in [1 + x + x^2 + x^3+.......+x^(k1)] ^ 365 that is coefficient of x^n in (1x^k)^365 * (1x)^(365) say is is m then using binomial theorem (verify it I have forgotten binomial coeff ) m = (364+n)C(n1)  365 * (364+nk)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 9^{th}, 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 K1 people ahead all have distinct birthdays AND your birthday matches one of theirs. Let A = event that your birthday matches one of the K1 people ahead B = event that those K1 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 Kth 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(K1) + P(K) = 1  Q(K) P(1) + P(2) + ... + P(K1) = 1  Q(K1) P(K) = Q(K1)  Q(K) < this is what we want to maximize. Now if the first K1 all have distinct birthdays, then assuming uniform distribution of birthdays among D days of the year, the Kth person has K1 chances out of D to match, and DK+1 chances not to match (which would produce K distinct birthdays). So Q(K) = Q(K1)*(DK+1)/D = Q(K1)  Q(K1)*(K1)/D Q(K1)  Q(K) = Q(K1)*(K1)/D = Q(K)*(K1)/(DK+1) Now we want to maximize P(K), which means we need the greatest K such that P(K)  P(K1) > 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(I1)  Q(I) = Q(I)*(I1)/(DI+1) Q(I)  Q(I+1) = Q(I)*I/D P(K)  P(K1) = P(I+1)  P(I) = (Q(I)  Q(I+1))  (Q(K2)  Q(K1)) = Q(I)*(I/D  (I1)/(DI+1)) To find out where this is last positive (and next goes negative), solve x/D  (x1)/(Dx+1) = 0 Multiply by D*(D+1x) both sides: (D+1x)*x  D*(x1) = 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: 1667


Re: Generalized Birthday "Paradox" (M)
« Reply #24 on: Dec 9^{th}, 2006, 8:37am » 
Quote Modify

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

« Last Edit: Dec 9^{th}, 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



