Seating in a cinema hall

Question

There are $N$ numebered seats in a cinema hall. Each seat has been assigned to a specific spectator. However, the first $N-1$ spectators arrive early and occupy the seats completely randomly. The last spectator wishes to occupy her allotted seat though. So she goes to her allotted seat and then there are two cases

1. if the seat is vacant, occupies it
2. if the seat is occupied then asks the person sitting there to vacate it. The person asked to vacate follows the same pattern : goes to their allotted seat and either sits there if it is vacant or asks the person sitting there to move if occupied. This goes on till everyone is in their correct seats.

What is the expected number of displacements caused in this process?

Answer 1

Let $\mu_k$ denote the expected number of displacements if there are $k$ specators.

Then: $$\mu_k=\frac{k-1}k\cdot(1+\mu_{k-1})=\frac{k-1}k+\frac{k-1}k\mu_{k-1}$$

One step further we find:$$\mu_k=\frac{k-1}k+\frac{k-1}k\mu_{k-1}=\frac{k-1}k+\frac{k-1}k\left(\frac{k-2}{k-1}+\frac{k-2}{k-1}\mu_{k-2}\right)=\frac{k-1}k+\frac{k-2}{k}+\frac{k-2}{k}\mu_{k-2}$$This makes us suspect that for $n<k$:$$\mu_k=\frac1k\sum_{i-1}^n(k-i)+\frac{k-n}k\mu_{k-n}$$ and this can be verified by induction.

This leads to $$\mu_N=\frac1N((N-1)+\cdots+1)+\frac1N\mu_1=\frac12(N-1)+0=\frac12(N-1)$$

Answer 2

The expected number of displacements caused in this process are $\frac{N-1}{2}$ because no matter how many people are at the cinema hall, on the average,exactly one of them will select his own seat. So the expected number of displacements are $\frac{N-1}{2}$.

Letting $X$ denote the number of spectators that select their own seats, we can best compute $E[X]$ by noting that

$X=X_1+X_2+...+X_N$ where $X_i=\left\{{1,\mbox{if the ith spectator selects his own seat}\atop 0,\text{otherwise}}\right.$

Now, because the ith spectator is equally likely to select any of the N seats, it follows that

$P(X_i=1)$=P(ith spectator selects his own seat)=$\frac1N$

and so

$E[X_i]=1*P(X_i=1)+0*P(X_i=0)=\frac1N$

Hence,we obtain

$E[X]=E[X_1]+...+E[X_N]=(\frac1N)*N=1$. Hence, no matter, how many people are at the cinema hall, expected number of spectator who will select his own seat is exactly 1

So the expected number of displacements are $\frac{N-1}{2}$