Quick Post: “n people line up to sit in an n-seat theater”
With a Nod to Schelling
On Twitter, Josh Wolfe posted the above problem, which asks:
100 people line up to take their seats in a 100 seat theater.
The 1st person in line lost her ticket and so sits in a seat at random.
Each remaining theatergoer sits in their assigned seat unless it’s occupied, in which case they sit in a seat at random.
What’s the probability that the last person in line sits in their assigned seat?
In the responses, the set of answers is about what one would expect for a somewhat subversive question such as this — with the most common mistake being 1/100 = 1%. Other kindred spirits estimated the correct answer by writing code to simulate the above scenario and watched how it converged. As someone who likes to simulate everything, I think that’s a reasonable play. But in this case, out-right simulating the above scenario doesn’t give much insight into the underlying problem, so it’s easy to miss the main takeaway: it actually doesn’t matter how many people/seats there are, the answer is always the same.1
First, approaching these sorts of problems is almost always easier when they’re phrased in terms of counting things rather than probabilities. So what are we counting here?
- The number of ways to fill the seats so that the last remaining seat is the last person’s assigned seat.
- The number of ways to fill the seats so that the last remaining seat is not the last person’s assigned seat.
- The relative frequencies of each of the previous outcomes.
Since the last remaining seat is either the last person’s assigned seat or not, (1) + (2) = the total number of ways to fill the seats. The number of combinations in which persons A through n-1 can choose a particular seat determines its relative frequency — e.g. if there are 3-seats, person A ends up in each seat 1/3rd of the time, but since they can end up in seat 2 in two different ways, person B’s choices then split those odds. Then summing over (3) for the last person’s correct seat assignment is the probability that the last person is in their correct seat.
Next, it’s almost always easier to count smaller things than larger things. When working with several small cases that are easy to visualize, relationships between the cases will often become apparent. In combinatorics, a recurrence relationship allows us to get the solution for the n+1 case by knowing the solutions for the smaller cases.2 So instead of jumping directly to the 100-seat scenario, let’s look at simpler scenarios:
- Let person A be assigned seat 1, person B be assigned seat 2, person C be assigned seat 3, etc. (without loss of generality)
In the 2-seat scenario, person A randomly takes either seat 1 or seat 2, and then person B must take the remaining seat. The possible outcomes are then:
It’s easy to see that the probability of person B sitting in their assigned seat is then (1/2).
When we move to the 3-seat theater, if the first two seats are filled according to the same pattern as the 2-seat scenario, then the only remaining option is for person C to sit in seat 3, and thus person C sits in their assigned seat in both cases. But there are also two new possibilities for persons A and B to fill the seats:
And again, the probability of person C sitting in their assigned seat is (1/3) + (1/6) = (1/2).
It turns out this pattern continues to hold. When adding a new person/seat, the first n-1 seats are either filled according to the n-1 case, in which case the new person must sit in their assigned seat, or the first n-1 seats are filled in such a way that seat 1 remains empty and the last person must sit in it. The sum of the relative frequencies of those two possibilities are equal at (1/2). To highlight the pattern:
(erratum: special thanks to Kid Dynamite for pointing out two errors in my original 4-seat chart, and then another one in my first correction)
Each of the things we’re counting in (1) and (2) are then equal and grow at the same rate. Thus, the probability is the same no matter what n we choose.
This exercise reminded me of some examples in Thomas Schelling’s Micromotives and Macrobehavior where there’s non-obvious, invariant aspects to different types of counting problems. I’m out of town now but I’ll update this with some specifics later.
Thanks to Jamie Pastore for just being Miley.
This post originally appeared on Zachary David’s Market Fails & Computational Gibberish.
- For 1 < n < infinity anyway. For some interesting weirdnesses at infinity, see Hilbert’s Hotel
- Often to get the n+1 case you need to not only know the n case but n-1 and further. Some fun stuff to study and work with are generating functions that attempt to take recurrence relationships and solve them in such a way so that you don’t need to keep track of a bunch of previous cases