Seating of $n$ people with tickets into $n+k$ chairs with 1st person taking a random seat

"$n$ music lovers have reserved seats in a theater containing a total of $n+k$ seats ($k$ seats are unassigned). The first person who enters the theater, however, lost his seat assignment and chooses a seat at random. Subsequently, people enter the theater one at a time and sit in their assigned seat unless it is already occupied. If it is, they choose a seat at random from the remaining empty seats. What is the probability that person $n$, the last person to enter the theater, finds their seat already occupied?" I could do this problem for small specific values of $n$ and $k$ but as they grow the expressions seem to get really messy really quick with no discernible pattern. How would one solve this problem?

$\begingroup$ I know that the answer is 1/2 when $k$ = 0, mostly because I've done this problem before. $\endgroup$

$\begingroup$ @eric The title of your questions does not convey any information. Can you change to something slightly more informative, maybe something like "Probability question with random seating" for example? That would help for future reference. $\endgroup$

4 Answers 4

Let $N=n+k$. I claim the probability that person $i$'s seat is taken already when she walks into the room is $\frac$, if $i>1$. We can prove this by induction. Indeed if $1

(The probability that $j$ takes seat $i$, if $j$ chooses a seat at random and nobody has yet taken seat $i$, is $1/(N-(j-1)$.)

Taking $i=n$, you get $1/(k+2)$.

There is a second, admittedly much nicer way to get this answer. Notice that as soon as anybody chooses any of the seats $1,n,n+1,\ldots,n+k$, the fate of person $n$ is sealed, because every subsequent person takes her own seat. Clearly each of the seats $1,n,\ldots,n+k$ is equally likely to be taken first, so the probability that seat $n$ is taken first is $1/(k+2)$.

I think that the easiest way to see the solution is by considering another problem: the first person takes a random seat. The persons arriving later go to their own seats no matter what - if their seat is already occupied, they ask the person occupying it to move away and to take a random seat amongst the seats still vacant. This is clearly equivalent to the original problem. Moreover, it's easy to solve. The first person has to change seats until ending up in one of the seats $1,n,n,n+1,\dots n+k$, each of these being equally likely. Thus the probability that the last person finds their seat already occupied is exactly $1/(k+2)$

$\begingroup$ What's most fascinating about this is how different it feels to the original problem, though as you say clearly equivalent. $\endgroup$

This is similar to a typical problem regarding passengers occupying seats in a plane.

By the time $r$ people are seated, the seats $2,3,\ldots,r$ are all occupied (if $i^\mathrm$ seat was unoccupied, $i^\mathrm$ person would have sat there, for $i \neq 1$). So $r-1$ seats are fixed. That one additional seat, if it was any of the $k$ extra seats, or if it was the seat $1$, then the remaining people sit in their places, in particular $n^\mathrm$ person will sit in seat $n$. But if this seat was $n$, then $n^\mathrm$ person cannot have seat $n$ now. Whichever of these two events occurs first, decides whether $n$ sits in seat $n$ or not. Suppose one of these events occurs first after $r$ seats are filled. So person $r$ either sat in 'seat $1$ or any of the extra $k$ seats' or in 'seat $n$'. So probability that person $n$ can sit in seat $n$ is $\frac$.

$\begingroup$ I didn't quite understand your reasoning in your last three sentences (the three starting with "so"). How did you derive the formula? $\endgroup$

$\begingroup$ Look at it this way. I have $3$ disjoint events $A$,$B$ and $C$ and I have to pick one of them at random (with probabilities $P(A)$, $P(B)$ and $P(C)$ respectively). If I pick $A$, I win. If I pick $B$, I lose. If I pick $C$, I start again and pick from $A,B,C$. You can show in this case that probability of winning is $P(A)/(P(A)+P(B))$. Our case is similar to this, but with a small difference. $\endgroup$

$\begingroup$ When $r$ people are seated, we noted that the seats $2,3,\ldots ,r$ are all occupied. Based on that one other seat which is occupied, the events here are '$A$ - seat $1$ or any of the extra $k$ is occupied', '$B$ - seat $n$ is occupied', '$C$ - everything else'. Note that this is now similar to the previous case, but the probabilities $P(A),P(B),P(C)$ do not remain same each time. But $P(A)/P(B)$ remains constant ($\frac$). So at each step probability of winning is some constant times probability of losing. Adding up these over all steps, we get the required answer. $\endgroup$

$\begingroup$ Why is $P(A)/P(B)$ a constant, and why is that constant $\frac$? Also, how did you add up to obtain $\frac$? Could you please write out the formula (with $\sum$ or whatever). $\endgroup$

$\begingroup$ Although the answer indeed appears to be $1-\frac<1>$, based on simulations, this answer does not do a good job of explaining why. $\endgroup$