A birthday puzzle

[jason_t]

This is a spin on a classic problem from probability. If you're familiar with that problem, this won't be that difficult but is still interesting.

The manager of a movie theatre announces that a free ticket will be given to the first person in line whose birthday is the same as someone else who has already purchased a ticket. You can get in line at any time. The birthdays are distributed uniformly at random over 365 days. Which position in line should you take?

[BruceZ]

[ QUOTE ]
This is a spin on a classic problem from probability. If you're familiar with that problem, this won't be that difficult but is still interesting.

The manager of a movie theatre announces that a free ticket will be given to the first person in line whose birthday is the same as someone else who has already purchased a ticket. You can get in line at any time. The birthdays are distributed uniformly at random over 365 days. Which position in line should you take?

[/ QUOTE ]

Answer in white:
<font color="white">You should stand 20th in line. </font>

[astarck]

Why?

Because this is the first position where the probability of two people in line sharing a birthday is greater than 50%.

To illustrate let's enumerate the first several people in line.
1st person: he's screwed since he is first...
2nd person: There is a 1/365 chance of a shared birthday
3rd person: There are now three combinations that result in a shared birthday, so 3/365.
4th person: now there are 6 combinations leading to a 6/365 chance that there is a shared birthday.

By now you should see the trend that is the probability of there being a shared birthday somewhere in the line at position n is given by
P(shared b-day)_n = Sum(i from 1 to n-1) of i/365

Solving this for n you find the optimal place is n=20. Wait any longer and the odds are greater than 50% that someone will claim the prize before you. Get in line any earlier and you will not have maximized your potential to win.

Of course, if your B-day is February 29 then you are just SOL.

[SheetWise]

[ QUOTE ]
3rd person: There are now three combinations that result in a shared birthday, so 3/365...

[/ QUOTE ]

The combinations don't do you any good. You need a match to win ... if another combination hits, it just means someone ahead of you in line won.

[SheetWise]

Probability, assuming all are unique - because otherwise somebody else won ...

01. 1/365
02. 1/182.5
03. 1/121.6
...

18. 1/20.3
19. 1/19.2 Cum = 19/19.2
20. 1/18.3 Cum = 20/18.3

I still like the idea of going with a twin brother or sister.

[SheetWise]

Are you assuming that the "player" values the opportunity and the ticket equally?

[LetYouDown]

Hrm. I took about 3 minutes to write a simple 20 line program to simulate this. Ran a quick 100,000 trial a couple times and the best spot seemed to average out to somewhere between 24.6 - 24.7. I wonder what I screwed up.

[jason_t]

[ QUOTE ]
Because this is the first position where the probability of two people in line sharing a birthday is greater than 50%.

[/ QUOTE ]

No. Even if it were true, that wouldn't necesarily provide the solution.

[SheetWise]

I wrote a simple simulation and ran 1MM a couple of times --20 came out as the highest frequency both times.

[kiddj]

I come up with 23rd. (It may be 22nd. I worked it with the chances that the people ahead have not paired up.) My line/logic may be flawed though.

[LetYouDown]

I'm still trying to figure out what I messed up. I just ran through an array with random numbers between 1-365 to represent the days (ignoring leap years). As I randomized each date, I compared it to all previous people in line. If it matched, saved it and continued to the next trial. Then I divided by the number of trials.

Edit: Is it more accurate to look for the most common occurring element or the mean for this problem?

[durron597]

You should stand 23rd in line. The reason being is that the more people in front of you, the more likely it is to have already occurred. Since 23 people is the number required for there to be at least 50% chance of two people having the same birthday, you expect that any spot after that in line it has already occurred.

[PairTheBoard]

Seems like it depends on how long the line is. If there's a billion people in line then someone will almost surely win after the first ticket is purchased. Your best chance of getting in on it would then seem to be by standing second in line.

PairTheBoard

[LetYouDown]

Huh?

[PairTheBoard]

[ QUOTE ]
Huh?

[/ QUOTE ]

Huh?

PairTheBoard

[LetYouDown]

Why would the number of people in line affect the likelihood of the 2nd person's birthday matching the first person's?

[Karatitis]

Because you would only have 1 birthdate in the pool to match against.

[PairTheBoard]

[ QUOTE ]
Why would the number of people in line affect the likelihood of the 2nd person's birthday matching the first person's?

[/ QUOTE ]

It wouldn't. But it would effect the chance of any person in line getting more than one shot at it. The game will be over as soon as the first ticket is bought. If you don't match birthdays with the first in line you are just out of luck because you won't get any more chances. But if you do match birthdays your most advantageous place to be is second in line so that someone in front of you who also matches won't take the prize away from you.

PairTheBoard

[jason_t]

[ QUOTE ]
You should stand 23rd in line. The reason being is that the more people in front of you, the more likely it is to have already occurred. Since 23 people is the number required for there to be at least 50% chance of two people having the same birthday, you expect that any spot after that in line it has already occurred.

[/ QUOTE ]

No.

[bobman0330]

your chance of winning with N other people = N/365 [you match someone] * (365!/((365-N)! * 365^N)) [no other matches]
Using this table of results for the latter expression (link (http://www.people.virginia.edu/~rjh9u/birthtable.html)):
N 365*P (for calculation ease)
18 11.754
19 11.799
20 11.780
21 11.676

This implies that you should want 19 people in front of you, which will allows you to win 3.23% of the time. This seems low, but I think it is right nonetheless.

You people should be ashamed of yourselves for Monte-Carloing this.

Note: the correct answer has nothing to do with when there's a 50% likelihood of someone having won before you. P(someone else winning) increases in an S-curve shape, while P(you winning, assuming no one else has won) increases linearly. The idea is to take advantage of as much of the linear increase as you can before the steep portion of the S starts killing your equity.

[FouTight]

[ QUOTE ]
[ QUOTE ]
Why would the number of people in line affect the likelihood of the 2nd person's birthday matching the first person's?

[/ QUOTE ]

It wouldn't. But it would effect the chance of any person in line getting more than one shot at it. The game will be over as soon as the first ticket is bought. If you don't match birthdays with the first in line you are just out of luck because you won't get any more chances. But if you do match birthdays your most advantageous place to be is second in line so that someone in front of you who also matches won't take the prize away from you.

PairTheBoard

[/ QUOTE ]

I can't pretent to want to figure out the right answer to this question, but this, without a doubt, is not it.

[LetYouDown]

[ QUOTE ]
You people should be ashamed of yourselves for Monte-Carloing this.

[/ QUOTE ]
LOL, normally I would be...but this computer doesn't have excel and I didn't feel like doing any computation. Also, I wanted to write a "monte-carloing" program because I was bored. Apparently I suck at doing it quickly.

[SheetWise]

[ QUOTE ]
If it matched, saved it and continued to the next trial. Then I divided by the number of trials.

[/ QUOTE ]

I just looked at frequency. 20 has the highest class frequency in every trial.

[SossMan]

it's not the chances of the guy in front of you having your birthday, it's anyone in front of you having your birthday.

[PairTheBoard]

[ QUOTE ]
[ QUOTE ]
[ QUOTE ]
Why would the number of people in line affect the likelihood of the 2nd person's birthday matching the first person's?

[/ QUOTE ]

It wouldn't. But it would effect the chance of any person in line getting more than one shot at it. The game will be over as soon as the first ticket is bought. If you don't match birthdays with the first in line you are just out of luck because you won't get any more chances. But if you do match birthdays your most advantageous place to be is second in line so that someone in front of you who also matches won't take the prize away from you.

PairTheBoard

[/ QUOTE ]

I can't pretent to want to figure out the right answer to this question, but this, without a doubt, is not it.

[/ QUOTE ]

Under the assumption that there are a billion people in line, what's wrong with it?

PairTheBoard

[bobman0330]

The explanation of the game stated that you win if someone in front of you has the same birthday...

[BruceZ]

[ QUOTE ]
[ QUOTE ]
[ QUOTE ]
[ QUOTE ]
Why would the number of people in line affect the likelihood of the 2nd person's birthday matching the first person's?

[/ QUOTE ]

It wouldn't. But it would effect the chance of any person in line getting more than one shot at it. The game will be over as soon as the first ticket is bought. If you don't match birthdays with the first in line you are just out of luck because you won't get any more chances. But if you do match birthdays your most advantageous place to be is second in line so that someone in front of you who also matches won't take the prize away from you.

PairTheBoard

[/ QUOTE ]

I can't pretent to want to figure out the right answer to this question, but this, without a doubt, is not it.

[/ QUOTE ]

Under the assumption that there are a billion people in line, what's wrong with it?

PairTheBoard

[/ QUOTE ]

It sounds like you are only taking one factor into account. The further back you are in line, the more chance there is that someone in front of you will match and take the prize away from you, that is true. The other factor is that the earlier you are in line, the less chance you have of matching anyone ahead of you. These two competing factors produce a maximum probability of first matching which happens to occur at the 20th position.

To win, two things must happen. First, everyone ahead of you must have different b-days, or else someone else will win. The number of ways that n people can have different b-days is 365*364*363*... (n terms) = 365!/(365-n)! = P(365,n). In Excel, P is the =PERMUT function. The total number of ways the n people can have b-days is 365^n, so the probability that no one ahead of you has the same b-day is P(365,n)/365^n. Now, when the n people in front of you have different b-days, the probability that one of them has your b-day is n/365. So all together, the probability that you win is:

P(365,n)/365^n * n/365.

This has a maximum of 3.232% at n=19, so we want 19 people ahead of us, meaning that we want to be 20th.

[jason_t]

[ QUOTE ]
[ QUOTE ]
[ QUOTE ]
[ QUOTE ]
[ QUOTE ]
Why would the number of people in line affect the likelihood of the 2nd person's birthday matching the first person's?

[/ QUOTE ]

It wouldn't. But it would effect the chance of any person in line getting more than one shot at it. The game will be over as soon as the first ticket is bought. If you don't match birthdays with the first in line you are just out of luck because you won't get any more chances. But if you do match birthdays your most advantageous place to be is second in line so that someone in front of you who also matches won't take the prize away from you.

PairTheBoard

[/ QUOTE ]

I can't pretent to want to figure out the right answer to this question, but this, without a doubt, is not it.

[/ QUOTE ]

Under the assumption that there are a billion people in line, what's wrong with it?

PairTheBoard

[/ QUOTE ]

It sounds like you are only taking one factor into account. The further back you are in line, the more chance there is that someone in front of you will match and take the prize away from you, that is true. The other factor is that the earlier you are in line, the less chance you have of matching anyone ahead of you. These two competing factors produce a maximum probability of first matching which happens to occur at the 20th position.

To win, two things must happen. First, everyone ahead of you must have different b-days, or else someone else will win. The number of ways that n people can have different b-days is 365*364*363*... (n terms) = P(365,n). In Excel, P is the =PERMUT function. The total number of ways the n people can have b-days is 365^n, so the probability that no one ahead of you has the same b-day is P(365,n)/365^n. Now, when the n people in front of you have different b-days, the probability that one of them has your b-day is n/365. So all together, the probability that you win is:

P(365,n)/365^n * n/365.

This has a maximum of 3.232% at n=19, so we want 19 people ahead of us, meaning that we want to be 20th.

[/ QUOTE ]

This solution is correct.

[PairTheBoard]

ok, I get it now. I was confused over the meaning of the phrase "The first person in line who..."

It evidently means, The First "first person in line" who ...

I took it to mean that if at any time, any person in line has a birthday matching one of the ticket purchasers, then the First such person in line wins the ticket. With a billion people in line almost certainly one of them will match the first ticket purchaser. I figured the birthday would be announced on a loudspeaker, there would be about 2,740,000 people in line with matching birthdays raising their hands, and the First of them in line would get the ticket.

Nevermind


PairTheBoard

[irchans]

Maybe we can find the flaw.

[KenProspero]

Alternate way of solving.

Excel Spreadsheet -- took about 2 minutes (longer to type this).

1. For each person on line, calculate the probability that there is a birthday match.

Person 1 -- 0.0000, Person 2 -- 1/365 (.00274), Person 3 2/365 (.005464) etc.

2. Determine the percentage chance that someone has not already won (this will be 1 - the sum of the probablilties determined in step 1 for all prior people).

3. For each person in line, multiply the amount in step 1 by the amount in step 2.

Relevant part of chart --

Person 19 .032207
Person 20 .03232
Person 21 .03225

Probablilities of winning increase to person 20 and decrease thereafter

[irchans]

Very Nice Ken.

[irchans]

Variation 1 (fairly easy if you can do the orignial variation)

The manager of a movie theatre announces that a free ticket will be given to the first person in line whose birthday and birth hour is the same as someone else who has already purchased a ticket. You can get in line at any time. The birthdays and hours are distributed uniformly at random over 365 days and 24 hours. Which position in line should you take?


Variation 2
(Hard. I don't think there is a closed form expression for the answer, but maybe good approximations exist.)

The manager of a movie theatre announces that a free ticket will be given to the first person in line whose random number is the same as someone else who has already purchased a ticket. You can get in line at any time. The random numbers are uniformly distributed integers ranging from 1 to N. Which position in line should you take? (The answer is a formula which depends on N.)

[pzhon]

[ QUOTE ]

Variation 2

The manager of a movie theatre announces that a free ticket will be given to the first person in line whose random number is the same as someone else who has already purchased a ticket. You can get in line at any time. The random numbers are uniformly distributed integers ranging from 1 to N. Which position in line should you take? (The answer is a formula which depends on N.)

[/ QUOTE ]
Actually, I think this might have been asked in this forum before.

Let P(k) be the probability that the first duplicate is the kth person in line.

P(k) = (N-1)(N-2)...(N-(k-2)) (k-1) / N^(k-1)

We'd like to know when P(k+1) is smaller than P(k). When this happens, we want to be the kth person in line.

P(k+1)/P(k) = (N-(k-1))k / (N (k-1))

After a little algebra, we see that this is 1 when k(k-1)=N, or when k = 1/2 + sqrt(N+1/4).

When 1/2 + sqrt(N+1/4) is an integer, it is equally good to stand in this place or the next. These are the optimal places. For example, when N=2, it is equally good to stand in place 0.5+sqrt(2.25)=2 and 3.

When 1/2 + sqrt(N+1/4) is not an integer, the optimal place is given by rounding 1/2 + sqrt(N+1/4) up to the next integer. For example, when N=365, you want position ceiling(0.5+sqrt(365.25)) = ceiling (19.61) = 20.

[irchans]

Lovely solution. I didn't sit down to figure it out before reading your post. I should have!

[TomCollins]

You are looking for:
P(No Birthday Found Before Me)*P(Someone's Birthday In Line is the same as mine | Unique Birthdays)

Call them 1-f(n) and g(n).

g(n) is easy, its (n-1)/365, where n is your position in line.

f(n) is a little more tricky, in essence, its "a birthday matched before me, or everyone before me is unique, and I match".

So f(n) = f(n-1) + (1-(f(n-1))*g(n).

These can be calculated out.

So the max of (1-f(n))*g(n) occurs when n = 20, so when there are 19 people in front of you.