Continuous-time Markov Chain for wrong seats on a plane

Question

I found this variation of the wrong seats on a plane problem.

A passenger plane with $N$ numbered seats is about to take off; $N-1$ seats have already been taken, and now the last passenger enters the cabin. The first $N-1$ passengers were advised by the crew, rather imprudently, to take their seats completely at random, but the last passenger is determined to sit in the place indicated on his ticket. If his place is free, he takes it, and the plane is ready to fly. However, if his seat is taken, he insists that the occupier vacates it. In this case the occupier decides to follow the same rule: if the free seat is his, he takes it, otherwise he insists on his place being vacated. The same policy is then adopted by the next unfortunate passenger, and so on. Each move takes a random time which is exponentially distributed with mean $\mu^{-1}$. What is the expected duration of the plane delay caused by these displacements?

What is the state space for this CTMC? In the classic problem of 100 seats and only the first passenger being unruly, how I imagined it is a "linked list" which closed on itself when a person finally sits in the correct seat. I am unsure of how to extend this idea to this CTMC problem. Would appreciate some insight!

Answer 1

We say that a passenger is "active" between the time they were requested to move until the time they got to their seat, (and then: either a new passenger is active or none is active, according to whether our passenger's seat was taken or not).

Let ${\bf X}=(X_t:t\ge 0)$ count the number of passengers that were activated by time $t$ if there is an active passenger at time $t$, and zero otherwise. Since no more than $N-1$ passengers can be activated, the state space is $0,\dots, N-1$.

Also, at time $0$, the chain is either equal to $0$ with probability $1/N$ (see calculation below) of equal to $1$ with probability $(N-1)/N$.

Now for the dynamics of the chain.

Clearly, if $X_t=0$, then $X_{t+s}=0$ for all $s\ge 0$ (none is active now then none will ever be activated). That is $0$ is absorbing. If $X_{t}=j$ for $j=1,\dots,N-1$, then at time $t$ we are looking at the $j$-th customer to be asked to move. Besides this customer, we have:

• the last customer to board: already seated in their place.
• $j-1$ customers previously activated, also seated in their places.
• $N-1-j$ customers, uniformly seated in the $N-j$ remaining seats.

There are $(N-j) \times \cdots\times 2$ ways to seat the last group of $N-1-j$ customers in the $N-j$ seats. There are $(N-j-1)!$ ways to seat them all in seats excluding the one belonging to our currently active customer. Therefore, the probability that the currently active customer's seat is available is $1/(N-j)$.

Since we assumed exponential rate $\mu$ from every state, the transitions (other states) from $j$ are to:

• $0$ with exponential rate $\mu / (N-j)$; or
• $j+1$ with rate $\mu * (N-j-1)/(N-j)$

Now for the expected delay. Call it $T$. It is simply the hitting time of state $0$ by the chain ${\bf X}$.

Let $M$ be the number of passengers to be ever activated. Observe that $P(M\ge 1) = \frac{N-1}{N}$ and $P(M\ge j+1| M\ge j)= \frac{N-j-1}{N-j}$. Therefore by induction, $P(M \ge j+1) = \frac{N-j-1}{N}$, $j=0,1,2,\dots,N-1$.

In other words, $M$ is uniform on $\{0,\dots,N-1\}$. As a result $E[M] =\frac{N-1}{2}$.

Since the time until absorption is the sum of $M$ independent exponential RVs with rate $\mu$, it follows that the expected time until absorption is $\mu^{-1} E[M]$, that is

$$E[T] = \mu^{-1}\frac{N-1}{2}.$$