Past exam of the mathematics course of the University of Cambridge / 2006 / ii / Paper 3 / 25J (Applied Probability)

Complete the random assignment by assigning passenger $N$ to the one vacant seat. This turns the uniformly random seating of the first $N-1$ passengers into a uniformly random permutation of all $N$ passengers. Following an occupant to the seat on their ticket traverses precisely the cycle containing $N$; the process ends at the initially vacant seat.

The cycle length of a tagged element in a uniform permutation is uniform on $\{1,\dots ,N\}$. Indeed, for length $\ell$, its count is $\left(\genfrac{}{}{0ex}{}{N-1}{\ell -1}\right)(\ell -1)!(N-\ell )!=(N-1)!$, out of $N!$ equally likely permutations. A cycle of length $\ell$ displaces $\ell -1$ already-seated passengers. The mean number of displacements is therefore $(N-1)/2$. Conditional on the cycle, summing the mean duration ${\mu }^{-1}$ of each displacement givesThis counts the delay caused by moving already-seated passengers, as the final wording suggests. If “each move” is intended also to charge the last passenger's own initial seating, even when their seat was vacant, the number of timed moves is $\ell$ instead, and the answer is $(N+1)/(2\mu )$. These conventions differ by the baseline boarding time ${\mu }^{-1}$; the distinction is present in the source wording.