Past exam of the mathematics course of the University of Cambridge / 2009 / ii / Paper 4 / 26J (Applied Probability)

Number the vertices $A,B,C$ by $0,1,2$. The continuous-time Markov chain moves one step forward cyclically at rate one, as shown in the left diagram.

Write $P$ for the cyclic shift matrix, so $Q=P-I$. With $\omega =e^{2\pi i/3}$, the eigenvalues of $P$ are $1,\omega ,{\omega }^2$ and those of $Q$ areThe stationary distribution is uniform. A jump count is a rate-one Poisson process, and the displacement is that count modulo three. The roots-of-unity filter $1_{n\equiv d(3)}=\frac{1}{3}{\sum }_{j=0}^2{\omega }^{j(n-d)}$ and $E(s^{N_t})=e^{t(s-1)}$ therefore give, for $d=(y-x)\mathrm{mod}3$,These are also the entries of $e^{tQ}$ obtained by diagonalizing $Q$. In particular,

The second continuous-time Markov chain runs in the reverse direction at rate $\rho$, as in the right diagram. Its nonzero eigenvalues have real part $-3\rho /2$, and its transition probabilities tend to $1/3$ for each vertex. Independence therefore givesThus the limit exists for every pair of starting vertices and equals $\boxed{1/3}$.

One can also see the limit directly without spectral multiplication. For fixed starting vertices, $X_t-Y_t$ modulo three advances with each jump of either flea. Its jump count is the sum of independent Poisson processes with rates $1$ and $\rho$, hence is Poisson with rate $1+\rho$ (multiply their generating functions). The formula from part (a), with $t$ replaced by $(1+\rho )t$ and the appropriate initial residue, gives $p(t)$ and the same limit.