Birthday Line Puzzle
There’s a line of ten people waiting to order at a café, when the proprietor says,
The first person in line, whose birthday this year is on the same weekday as anyone in front of them, will get a free muffin with their order.
You’re standing in eighth place. What’s the probability that you get a free muffin, and which person should you ask to swap with, to maximise your probability? What would your chances be if you manage to swap?
First, gut feel your way to an approximation. You can be surprisingly sloppy at this and still get a good reasult – we’ll get back to that. Then try to work out the exact answer.
Answer
Here’s some airy typographical stuff I don’t remember the name of to move the answer below the fold, in case you want to try to figure it out for yourself.
Fun fact: the asterisks are an html <hr> element styled with css.
Okay, stop scrolling if you don’t want the answer. It comes after the next ruler.
In place 8, you have a 1 % chance of getting a free muffin, and you want to switch places with person number 4, which will give you a whopping 26 % chance! But in fact, if your gut feel told you to swap into any place 3–5, you would have had a good chance. Places 2 and 6 are also a strong improvement over 8.
Look at that! If your gut feel told you anywhere in the range 2–6, you were good. There’s a reason such a sloppy approximation works, and at the end of this article we can see why. First up is how to figure out the exact answer.
Analysis
This is a very tricky problem. That took me multiple tries and a day of thinking to get a solution that’s actually correct.1 Adding to my confusion is that in the version of this I heard first, my incorrect solutions actually led to the right answer by coincidence. I’ve changed the problem slightly for this article to prevent that. One of the things that makes the problem interesting is that we have two opposing forces to balance out: the further back you stand, the more likely is it that someone ahead of you celebrates their birthday on the same day of the week as you – but on the other hand, the less likely it is that you are the first in line for which this is true.
We will break analysis down into those two components2 There’s a good reason we do it in this order. One of the reasons this problem is tricky is that the probabilities involved may seem independent, but they aren’t. By calculating them in the right sequence we make it easier to understand how to combine them.:
- First we will figure out the probability of not having lost (due to another pair of people sharing a birthday in front of us).
- Then, not having lost, we figure out the probability of going on to win (by having a birthday on the same day of the week as someone in front of us).
We can combine these two probabilities for our solution.
Probability of Everyone in Front of Us Having a Unique Birthday
Our first job is to figure out the probability that everyone ahead of us in the line have a unique birthday3 You might recognise this as “the birthday paradox” – it’s the exact same problem, but since I don’t remember its solution, I find it easier to work it out from basic principles., since this is a requirement for us not to lose.
We can compute it recursively. Take person 5 as an example. If we assume that everyone in front of person 5 has a unique birthday, then the probability that everyone up to and including person 5 has a unique birthday is given by (7 - 4)/7 = 0.43 %. This is because there are seven possible birthdays in total, but four of them must be taken already (the four in front each had different birthdays from each other), so there are only 7-4 = 3 birthdays left for person 5 to have and still have a unique birthday.4 When I speak of “unique birthdays” in this article, it’s meant to be interpreted in context, i.e. that the people up to and including the person we are discussing celebrate their birthdays on separate days of the week. Importantly, it does not say anything about the people behind in line.
We compute these numbers for all positions in line, and fill them into column A of a spreadsheet.5 Clamping the probability to be non-negative.
| Row | A | B | C | D |
|---|---|---|---|---|
| 1 | 1.00 | |||
| 2 | 0.86 | |||
| 3 | 0.71 | |||
| 4 | 0.57 | |||
| 5 | 0.43 | |||
| 6 | 0.29 | |||
| 7 | 0.14 | |||
| 8 | 0 | |||
| 9 | 0 | |||
| 10 | 0 |
In column A we assume that everyone in front of person 5 has a unique birthday. What’s the probability of that? Well, it’s the probability that everyone in front of person four has a unique birthday and that person four has a birthday also different from everyone in front. This is the recursion! In mathematical terms,
\[P(n\;\mathrm{unique}) = P(n\;\mathrm{unique} \mid n - 1\;\mathrm{unique}) \times P(n-1\;\mathrm{unique}) .\]
The base case of this recursion is 1 – whichever day of the week the first person celebrates, they’re definitely first in line to do so. In the spreadsheet, each row of column B is given by the product of the corresponding cell in column A, and the previous cell in column B.
| Row | A | B | C | D |
|---|---|---|---|---|
| 1 | 1.00 | 1.00 | ||
| 2 | 0.86 | 0.86 | ||
| 3 | 0.71 | 0.61 | ||
| 4 | 0.57 | 0.35 | ||
| 5 | 0.43 | 0.15 | ||
| 6 | 0.29 | 0.04 | ||
| 7 | 0.14 | 0.01 | ||
| 8 | 0 | 0 | ||
| 9 | 0 | 0 | ||
| 10 | 0 | 0 |
Once we get to person 8, we are guaranteed to have at least two people sharing their birthday. This is clear also from the pigeonhole principle: there is no way to spread out 8 birthdays over the 7 days of the week without at least two birthdays happening on the same day of the week.
So – then – what is the probability that we have not lost to another pair of people? Since we stand in position 8, it might be tempting to say 0 %, but the answer is actually 1 %, because the question we’re asking is whether no people ahead of us share some birthday. That probability is stored in row 7.
Now that we have this first component, the probability that we have not yet lost, we can move on to the probability that we subsequently win!
Probability of Us Sharing a Birthday With Someone in Front
For a long time I made a mistake here. What we really want to find out is the probability that we share a birthday with someone ahead of us, given that everyone ahead of us has a unique birthday. The last condition is important, because this probability matters only if we haven’t already lost.6 My mistake was that I assumed the probability of person \(i+1\) sharing a bitrhday with someone ont of tehm would be \(1 -(6/7)^i\), because there are 6 days of the week that are not the birthday of i+1, and i people in front of i+1 must have birthdays on any of those days in order for the birthday of i+1 to be unique. But is is incorrect because it assumes independence where it doesn’t exist. The event that we share a birthday with someone ahead of us is correlated with whether the people ahead of us already share birthdays or not. If the people ahead of us all have unique birthdays, that actually improves our chances of sharing a birthday with any of them, because their birthdays are more evenly distributed over the days of the week.
That probability is based just on the number of people ahead of us: if there’s
one person ahead of us, then that’s one day of the week we have to share. If
there are two people ahead of us, then that’s two days of the week we can share,
and so on.7 Remember, for this conditoinal probability we have to assume that
no people ahead of us share a birthday. The equation for column C is =(ROW() -
1)/7, clamped to the range 0–1.
| Row | A | B | C | D |
|---|---|---|---|---|
| 1 | 1.00 | 1.00 | 0 | |
| 2 | 0.86 | 0.86 | 0.14 | |
| 3 | 0.71 | 0.61 | 0.29 | |
| 4 | 0.57 | 0.35 | 0.43 | |
| 5 | 0.43 | 0.15 | 0.57 | |
| 6 | 0.29 | 0.04 | 0.71 | |
| 7 | 0.14 | 0.01 | 0.86 | |
| 8 | 0 | 0 | 1.00 | |
| 9 | 0 | 0 | 1.00 | |
| 10 | 0 | 0 | 1.00 |
We can already see the opposing influences of the two effects from columns B (previous section, probability of not losing) and C (this section, probability of winning).
Probability of Free Stuff!
We’re pretty much done here. The probability of getting a free muffin is, in mathematical terms,
\[P(\mathrm{free\;muffin}) = P(\mathrm{shared\;birthday} \mid \mathrm{unique\;ahead}) \times P(\mathrm{unique\;ahead})\]
Since the probabilities in column C are conditional on the probabilities in column B, we can multiply column C by the previous row of column B, and this will give us the answer to the puzzle.
| Row | A | B | C | D |
|---|---|---|---|---|
| 1 | 1.00 | 1.00 | 0 | 0 |
| 2 | 0.86 | 0.86 | 0.14 | 0.14 |
| 3 | 0.71 | 0.61 | 0.29 | 0.24 |
| 4 | 0.57 | 0.35 | 0.43 | 0.26 |
| 5 | 0.43 | 0.15 | 0.57 | 0.20 |
| 6 | 0.29 | 0.04 | 0.71 | 0.11 |
| 7 | 0.14 | 0.01 | 0.86 | 0.04 |
| 8 | 0 | 0 | 1.00 | 0.01 |
| 9 | 0 | 0 | 1.00 | 0 |
| 10 | 0 | 0 | 1.00 | 0 |
Thus at place 8 in the line, we have a measly 1 % probability of getting a free muffin. Infinitely better than the sucker behind us, but that’s not very comforting. It’s also clear we should tap number 4 on the shoulder, and perhaps try to convince them that it’s more likely they’ll share a birthday with someone in front if they stand further back!
Larger Parameters, Visual Solution
When I heard this puzzle, it was presented not with weekdays, but sharing actual birthdays during the year. That’s probably a more normal thing to compare, but the weakness of that version is that you can get a lot of your calculations wrong and still arrive at the right answer8 I know because that happened to me!.
It can still be instructive to look at what that does. The calculations are the same, except we now have 365 days to contend for, rather than just 7. If we plot contents of columns B, C, and D under that variant, we get the following.
Reminder:
- Column B (red) corresponds to the probability that everyone up to that point have a unique birthday. This probability starts off high and then drops off fairly quickly. This makes sense: we don’t need very many people to accidentally have two that share a birthday.
- Column C (green) corresponds to the probability that that person in line shares a birthday with someone ahead of them, given that everyone ahead of them have a unique birthday. This increases linearly as there are more people ahead, because (by virtue of them having unique birthdays) the surface area to hit grows by one day for each person.
- Column D (blue) contains the solution: this is the combined effect of not losing (column B) and then going on to win ( column C).
We can see that in this version, the chance of winning – in any position – is fairly slim. We optimise it at position 20, where there’s a 3.2 % chance that we win.
Optimisation of Mound-Shaped Things
But! If we zoom in on just the final probabilities, we may realise something else.
At the top of this hill, it’s rather flat. It doesn’t matter much for our chance of winning if we mis-estimate a few positions to the front or the back. Even if our estimation has an uncertainty of a quarter (i.e. we’re off by 5 from the optimum of 20) we still don’t hurt our chances by more than 10 %.
This is a general rule of thumb: whenever you need to find the maximum of a mound-shaped function, it’s fine if you’re off by a little. It’s rather flat on top. Don’t sweat over accuracy there. This is also why the problem with the weekdays was so generous in the face of misestimation.
An astute follow-up question would be How do we know when a function is mound-shaped, before computing it? Any time we’re trading off two things against each other, if we squint, they’re two opposing straight lines intersecting (check the previous image to see this in action in the birthday line problem.) Where they meet, there is usually something mound-like.