This problem was brought to my attention on G+, but I wasn’t satisfied with the solution presented. There are actually two versions, the one that was originally presented on G+ and the corrected one that matches the standard version. I’ll discuss the standard version first.
Standard version: All seats on an airplane are assigned. However, the first person to get on the plane doesn’t understand this and sits where he pleases (completely randomly). After this, if a passenger boards and finds their seat taken, they’ll randomly choose another seat; if they find their seat empty, they sit in it. What is the probability that the last passenger will sit in his own seat?
Let us call the first passenger A and the last passenger Z. We identify the following events:
- \(S_A\): A passenger sits in A’s seat.
- \(S_Z\): A passenger sits in Z’s seat.
- \(S_O\): A passenger sits in their own seat.
- \(S_D\): A passenger sits anywhere else.
For the first passenger, there is an equal probability that he will sit in either his own seat or in Z’s. That is, \(P(S_A) = P(S_Z)\). This is the key observation to solving this problem, as well as to extending the solution to the modified version.
If either of these events (\(S_A\) and \(S_Z\)), all the rest of the passengers sit in their assigned seats. Since \(P(S_A) = P(S_Z)\), the probability that Z sits in his own seat is 50%.
If the first passenger sits anywhere else, we have two scenarios for each of the other passengers: Somebody is sitting in their seat, or their seat is empty. If their seat is empty, then they sit there and have no effect on where Z sits (\(P(S_A) = P(S_Z) = 0\)). If their seat is taken, then they choose another seat randomly. Since their seat is taken, this means that both A’s seat and Z’s seat are empty (I’ll demonstrate this with an example in a moment), so \(P(S_A) = P(S_Z)\).
Let’s say there are 10 passengers: A, B, C, D, E, F, G, H, I, and Z. If A sits in D’s seat, then B and C sit in their own seats and D has this pool of seats to choose from: {A, E, F, G, H, I, Z}. If D sits in G’s seat, then E and F sit in their own seats and G has this pool of seats to choose from: {A, H, I, Z}. The point is that the constraints create a single chain of displacement: Each passenger either sits in their own seat, or is part of this chain. Because \(P(S_A) = P(S_Z)\) each time there’s a choice, we can ignore all the other probabilities. For each passenger, if \(S_A\) or \(S_Z\), the simulation ends and all the rest of the passengers sit in their own seat. If \(S_D\), then the passenger displaces a later passenger, and the process is repeated.
Hence, the probability that Z will sit in his own seat is exactly 50%.
If all of the passengers are allowed to sit where they please (regardless of whether or not someone’s already sitting in their seat), that’s a different scenario, although the solution is still straightforward: If there are n seats on the plane, then the probability that Z will sit in his own seat is 1/n.
The modified problem that was originally posted in G+ was, in paraphrase,
Modified version: All seats on an airplane are assigned. However, the first person to get on the plane is a troublemaker. Half the time, he sits in his assigned seat; the other half, he sits where he pleases (completely randomly, except not in his own seat). After this, if a passenger boards and finds their seat taken, they’ll randomly choose another seat; if they find their seat empty, they sit in it. What is the probability that the last passenger will sit in his own seat?
It’s easy to see why the answer is not 50% in this case: There’s a 50% chance that A will sit in his own seat, and situations where A sits in some other seat and Z sits in his own seat. For instance, if there are three passengers, we could have any of these seatings:
- (A, B, Z)
- (B, A, Z)
- (Z, A, B)
- (Z, B, A)
Note that this is not all the possible permutations, since two ((A, Z, B) and (B, Z, A)) violate the constraints because B’s seat would be empty at the time B boards the plane. Also note that these permutations do not have an equal likelihood of occurrence, in either the standard or modified versions. In the standard version, these are the probabilities:
- (A, B, Z): \(\frac{1}{3}\)
- (B, A, Z): \(\frac{1}{3} \cdot \frac{1}{2} = \frac{1}{6} \)
- (Z, A, B): \(\frac{1}{3} \cdot \frac{1}{2} = \frac{1}{6} \)
- (Z, B, A): \(\frac{1}{3}\)
If we add the probabilities of the first two cases, \(\frac{1}{3} + \frac{1}{6} = \frac{1}{2} \).
For the modified version, here are the probabilities:
- (A, B, Z): \(\frac{1}{2}\)
- (B, A, Z): \(\frac{1}{2} \cdot \frac{1}{2} \cdot \frac{1}{2} = \frac{1}{8} \)
- (Z, A, B): \(\frac{1}{2} \cdot \frac{1}{2} \cdot \frac{1}{2} = \frac{1}{8} \)
- (Z, B, A): \(\frac{1}{2} \cdot \frac{1}{2} = \frac{1}{4} \)
If we add the probabilities for the first two cases, \(\frac{1}{2} + \frac{1}{8} = \frac{5}{8} \).
In this case, we have to treat A’s seating differently than that of the rest. There is a 50% chance that A will sit in his own seat. The chance that he will sit in Z’s seat is \(\frac{1}{2} \cdot \frac{1}{n-1} = \frac{1}{2(n-1)}\), where n is the number of seats on the plane. The chance that he will sit elsewhere is \[1 – \frac{1}{2} – \frac{1}{2(n-1)} = \frac{2(n-1) – (n-1) – 1}{2(n-1)} = \frac{n – 2}{2(n-1)}\]
If he sits elsewhere, we have the same basic scenario we did before: Each passenger after A (other than Z) has the same chance of sitting in A’s seat or in Z’s seat, so there’s a 50% probability. This gives us the total probability that Z will sit in his own seat: \[\frac{1}{2} + \frac{1}{2}\cdot\frac{n – 2}{2(n-1)} = \frac{2(n-1)}{4(n-1)} + \frac{n-2}{4(n-1)} = \frac{3n – 4}{4n – 4} \]
We can verify this already for n = 3. Let’s check it as well for n = 4. If n = 4, then the probability that Z sits in his own seat is \(\frac{3(4)-4}{4(4)-4} = \frac{8}{12} = \frac{2}{3} \). Let’s consider the possibilities. A could sit in any of four seats:
- (A, ___, ___, ___): \(\frac{1}{2}\)
- (___, A, ___, ___): \(\frac{1}{6}\)
- (___, ___, A, ___): \(\frac{1}{6}\)
- (___, ___, ___, A): \(\frac{1}{6}\)
B has no choice in three of these situations, but has three choices in the second case:
- (A, B, ___, ___): \(\frac{1}{2}\)
- (B, A, ___, ___): \(\frac{1}{6} \cdot \frac{1}{3} \)
- (___, A, B, ___): \(\frac{1}{6} \cdot \frac{1}{3} \)
- (___, A, ___, B): \(\frac{1}{6} \cdot \frac{1}{3} \)
- (___, B, A, ___): \(\frac{1}{6} \)
- (___, B, ___, A): \(\frac{1}{6} \)
C has no choice in four of these situations, but has two choices in two cases. Z then has no choices:
- (A, B, C, Z): \(\frac{1}{2}\)
- (B, A, C, Z): \(\frac{1}{6} \cdot \frac{1}{3} = \frac{1}{18} \)
- (C, A, B, Z): \(\frac{1}{6} \cdot \frac{1}{3} \cdot \frac{1}{2} = \frac{1}{36} \)
- (Z, A, B, C): \(\frac{1}{6} \cdot \frac{1}{3} \cdot \frac{1}{2} = \frac{1}{36} \)
- (Z, A, C, B): \(\frac{1}{6} \cdot \frac{1}{3} = \frac{1}{18} \)
- (C, B, A, Z): \(\frac{1}{6} \cdot \frac{1}{2} = \frac{1}{12} \)
- (Z, B, A, C): \(\frac{1}{6} \cdot \frac{1}{2} = \frac{1}{12} \)
- (Z, B, C, A): \(\frac{1}{6} \)
Z is sitting in his own seat in cases 1, 2, 3, and 6. We add these probabilities up: \(\frac{1}{2} + \frac{1}{18} + \frac{1}{36} + \frac{1}{12} = \frac{18 + 2 + 1+ 3}{36} = \frac{24}{36} = \frac{2}{3} \). This is what we predicted.
Notice that the limit of this probability is not \(\frac{1}{2}\), as we might intuitively predict; nor is it 1. It is actually \(\frac{3}{4}\)… which does make sense, being \(\frac{1}{2} + \frac{1}{2}\cdot\frac{1}{2}\) (that is, the probability that A will sit in his own seat plus the probability that Z sits in his own seat if A doesn’t sit in either his own or Z’s).