Solving a modified birthday problem at a glance

Question

Modified Birthday Problem: a bunch of people line up, and the winner is the first person who shares their birthday with someone lined up ahead of them. 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.

Answer 1

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.

Answer 2

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.

Answer 3

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