Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Modified Birthday Problem: a bunch of people line up, and the winner is the first person who shares his birthday with someone lined up ahead of him. What position in the line is optimal?

Three (similar) approaches: Recall the well known Birthday Problem, and let $b(n)$ denote the likelihood that there is a shared birthday in a collection of $n$ people. Suppose you are the $(n+1)$st person in line, and you want to be the first person to share your birthday with someone ahead of you. 'None of the people ahead of you sharing a birthday' happens with probability $1 - b(n)$, and 'you sharing a birthday with one of them' happens with probability $n/365$. Therefore, we wish to maximize: $(1-b(n))(n/365)$. A computer search (e.g. in WolframAlpha) can find $n$ is about $19$, and so you want position $20$.

Alternatively, we can approximate $1-b(n)$ with $e^{-n(n-1)/730}$ pretty well. Now consider setting $\frac{d}{dx} e^{-x(x-1)/730} (x/365) = 0,$ which ends up requiring only that we solve a quadratic. In particular, we end up with the quadratic $x^2 - x/2 = 365.$ Then $x$ is a little over $19$, and again we guess the optimal position is at $20.$

Finally, we consider the ratio of probabilities of winning for consecutive people in line. Eliding over some details (e.g. showing initial ratio $> 1$, the ratios are decreasing) we can check to see when this ratio drops below $1.$ This will again culminate in solving a quadratic, namely, $x^2 - x = 365.$ Since $x$ is about $19$, we have (for the third time) found the optimal position to be at $20.$

Question 0: Why do the quadratics arrived at in our second and third approach differ? (I suspect this is just an artifact of the rough estimation used in the second approach, although I could not explain the reasoning behind this difference in any greater detail.)

Question 1: Since our third method indicates that solving for $x$ in $x(x-1) = 365$ ultimately leads to the solution, I am wondering: is there a way to have seen "at a glance" the importance of this quadratic? My intuition tells me that there is a much more straightforward way of thinking about this problem, but I am not sure what it would be.

share|improve this question
add comment

3 Answers

up vote 6 down vote accepted

The approaches in the OP already seem quite straightforward to me, and as is clear from the answer by Arthur B, doing the calculation exactly is not too complicated.

Anyway, here is my suggestion (after a bit of scribbling) for how one might have seen the solution at a glance.

All we have to do is compare the winning chances of person $k$ and person $k+1$ (provided we do it for general $k$). Edit: this is because the winning chances are first increasing and then decreasing, which of course isn't clear a priori, so perhaps the previous sentence should have started "As it turns out...".

We imagine two persons A and B who are to occupy places $k$ and $k+1$. We only have to compare the scenarios where the one who goes first wins, to the scenarios where the one who goes second wins (otherwise the order of A and B doesn't matter).

Those scenarios first of all require that persons $1,\dots, k-1$ have different birthdays.

Under that assumption, the cases where the person to go first wins are when both A and B have a birthday which is already represented among the first $k-1$ people. Counting combinatorially rather than probabilistically, there are $(k-1)^2$ ways of choosing the birthdays of A and B with that constraint.

The cases where the person to go second wins are when A and B have the same birthday, and that birthday is not shared with any of the first $k-1$ people. There are $n-(k-1)$ such ways of choosing the birthdays of A and B.

Therefore we end up comparing $(k-1)^2$ to $n-(k-1)$, or equivalently comparing $k(k-1)$ to $n$.

After having written it down, I get the feeling that this argument is more convoluted than the straightforward calculation by Arthur B, but here it is, for what it's worth.

share|improve this answer
    
I'm concerned you've missed other cases in which A or B can win. You are assuming that A wins only when both A and B share a birthday with someone ahead of them, and B wins only when A and B share a birthday (with one another) that hasn't yet appeared. Omitted case in which A wins: A's birthday is among the first k-1 birthdays, but B's birthday is not. Omitted case in which B wins: A's birthday is not among the first k-1 birthdays, but B's birthday is. –  Benjamin Dickman Aug 4 '12 at 17:00
    
Benjamin, those cases are not omitted, they are canceling each other. We compare the winning chances in positions $k$ and $k+1$, and therefore we only need to consider situations where the winner would change if we switch persons $k$ and $k+1$. Those are of only two types; those where the person in position $k$ wins regardless of whether it's A or B, and those where the person in position $k+1$ wins no matter if it's A or B. But the need to sort these things out is precisely why this can't reasonably be seen "at a glance" anyway. –  Johan Wästlund Aug 4 '12 at 20:56
    
Great - thanks! –  Benjamin Dickman Aug 12 '12 at 23:41
add comment

First, I want to establish the result properly

If there are $N$ dates ($N = 365$) then the probability that the person in position $k$ wins is the probability that persons $1\ldots(k-1)$ have distinct birthdates and that person $k$ has a birthday matching one of these $(k-1)$ distinct birthday, thus

$$p(w=k) = \frac{N!}{(N-k+1)!N^{k-1}} \frac{k-1}{N} = \frac{N!(k-1)}{N^k(N-k+1)!}$$

As you suggest, we can look at the ratio of successive terms, for $k>1$ $$\frac{p(w=k+1)}{p(w=k)} = \frac{k(N-k+1)}{(k-1)N}$$ It starts at a maximum of $2(N-1)/N$ and decreases monotonously to 0. The maximum is achieved for the lowest $k$ for which $k^2-k>=N$.

For 365 days, this gives $k=20$ as you point out.

I can't get the first quadratic exactly from a glance, but we should expect the answer to be $O(N^{1/2})$ as the number of potential collisions increases roughly like the square of the number of people considered at first.

share|improve this answer
add comment

First: we are ignoring leap years.

This means that if we have a line of 366 people, two of them must share a birthday.

Also, the first person in line cannot win.

So the sum of probabilities for the remaining 365 positions must total to 1.

Meanwhile, since only one person can win, we know that all positions ahead of the winner have distinct birthdays (and we do not know or care about the positions following the winner).

The base chance to win (ignoring other possibilities) thus increases linearly.

The base chance to be beaten increases quadratically (it's the sum of the base chance to be beaten, by each of your predecessors).

(to be continued...)

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.