# 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... – Joe Z. Jan 30 '13 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. – PatrickR Jan 30 '13 at 4:17
Here's the $k=0$ case: math.stackexchange.com/questions/5595/taking-seats-on-a-plane – Byron Schmuland Mar 18 '13 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)$.

-
+1 Sean, Thank you very much. Exactly the kind of answer I think this question deserves. – user40314 Mar 18 '13 at 17:20

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. – Sean Eberhard Mar 18 '13 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? – user54609 Jan 31 '13 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. – polkjh Feb 1 '13 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. – polkjh Feb 1 '13 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). – user54609 Feb 1 '13 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. – user40314 Mar 18 '13 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}}$$.

-