wu :: forums « wu :: forums - Generalized Birthday "Paradox" (M) » Welcome, Guest. Please Login or Register. Jan 16th, 2022, 6:03pm RIDDLES SITE WRITE MATH! Home Help Search Members Login Register
 wu :: forums    riddles    hard (Moderators: ThudnBlunder, SMQ, Grimbal, william wu, towr, Icarus, Eigenray)    Generalized Birthday "Paradox" (M) « Previous topic | Next topic »
 Pages: 1 2 Reply Notify of replies Send Topic Print
william wu

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
william wu

Gender:
Posts: 1291
 Re: Generalized Birthday "Paradox" (M)   « Reply #2 on: Sep 29th, 2003, 9:44pm » Quote 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:
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.
william wu

Gender:
Posts: 1291
 Re: Generalized Birthday "Paradox" (M)   « Reply #4 on: Sep 30th, 2003, 9:14am » Quote 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:
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

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

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:
 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 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 :
 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
Secret_mind
Guest

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

 IP Logged
Kishor
Newbie

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

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

Kishor
 IP Logged
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:
 It's 23.

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
 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: 1667
 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
 Pages: 1 2 Reply Notify of replies Send Topic Print

 Forum Jump: ----------------------------- riddles -----------------------------  - easy   - medium => hard   - what am i   - what happened   - microsoft   - cs   - putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »