# 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?

• I know that the answer is 1/2 when $k$ = 0, mostly because I've done this problem before... Jan 30, 2013 at 4:02
• @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. Jan 30, 2013 at 4:17
• Here's the $k=0$ case: math.stackexchange.com/questions/5595/taking-seats-on-a-plane
– user940
Mar 18, 2013 at 16:41

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

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

• What's most fascinating about this is how different it feels to the original problem, though as you say clearly equivalent. Mar 18, 2013 at 20:34

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}$.

• I didn't quite understand your reasoning in your last three sentences (the three starting with "so"). How did you derive the formula? Jan 31, 2013 at 18:53
• 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. Feb 1, 2013 at 4:57
• 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{k+1}{1}$). 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. Feb 1, 2013 at 5:06
• Why is $P(A)/P(B)$ a constant, and why is that constant $\frac{k+1}{1}$? Also, how did you add up to obtain $\frac{k+1}{k+2}$? Could you please write out the formula (with $\sum$ or whatever). Feb 1, 2013 at 19:31
• Although the answer indeed appears to be $1-\frac{1}{k+\min(n,2)}$, based on simulations, this answer does not do a good job of explaining why. Mar 18, 2013 at 16:20

So n music lovers(ML) may together with the empty seats to be arranged $(n + k)!$ ways.
That's the last the ML could sit down properly, so its location must be empty. It can be (k + 1) ways. While each of these free seats arrangement may occur $(k+n-1)!$ times.
The likelihood, that the viewer will have the seat free is $p ={{(k + 1)(k+n-1)!}\over {(n + k)!}}$. Because $(n+k)! = (n+k)(n+k-1)!$, the probability is:$$p = {{k+1}\over{k+n}}$$.