

Title: Generalized Birthday "Paradox" (M) Post by william wu on Sep 25^{th}, 2003, 12:44pm 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:
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:
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:
*Sigh* I guess that means my halfbrother 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:
That's the reason why it is common practice around here to hide (http://www.ocf.berkeley.edu/~wwu/cgibin/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/cgibin/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:
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!/(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: 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)*(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. 

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:
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 (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 [/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 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.[/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:
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:
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:
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
[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:
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:
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:
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:
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:


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:
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:
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!/((365n)!(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!(n3)!))*365 / 365^n and two people: (n!/(2!(n2)!))*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? 

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