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?

Solution 1:

Let $N=n+k$. I claim the probability that person $i$'s seat is taken already when she walks into the room is $\frac{1}{N-i+2}$, if $i>1$. We can prove this by induction. Indeed if $1<j<i$ then, by induction, the probability that $j$ chooses a seat at random is $\frac{1}{N-j+2}$, so the probably that somebody takes $i$'s seat is

$$\frac{1}{N} + \sum_{1<j<i} \frac{1}{N-j+2}\frac{1}{N-(j-1)} = \frac{1}{N} + \sum_{1<j<i} \left(\frac{1}{N-(j-1)}-\frac{1}{N-(j-2)}\right) = \frac{1}{N-i+2}.$$

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

Solution 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)$

Solution 3:

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{th}$ seat was unoccupied, $i^\mathrm{th}$ 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{th}$ person will sit in seat $n$. But if this seat was $n$, then $n^\mathrm{th}$ 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{k+1}{k+2}$.