A birthday puzzle

[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

[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.

[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):
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.

[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.

[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.