This article is from the Puzzles FAQ, by Chris Cole chris@questrel.questrel.com and Matthew Daly mwdaly@pobox.com with numerous contributions by others.

At a movie theater, the manager announces that they will give a free ticket

to the first person in line whose birthday is the same as someone who has

already bought a ticket. You have the option of getting in line at any

time. Assuming that you don't know anyone else's birthday, that birthdays

are distributed randomly throughtout the year, etc., what position in line

gives you the greatest chance of being the first duplicate birthday?

probability/birthday/line.s

Suppose you are the Kth person in line. Then you win if and only if the

K-1 people ahead all have distinct birtdays 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 then the old

is therefore I=19, and so K = I+1 = 20. You should try to be the 20th

person in line.

Computing your chances of actually winning is slightly harder, unless

you do it numerically by computer. The recursions you need have already

been given.

-- David Karr (karr@cs.cornell.edu)

Continue to: