= Solution
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.
\Image[/past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2009/ii/paper-4-fleas.png]
{title=Cyclic transitions of the two fleas, with their jump rates}
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$ are
$$
\boxed{0,\quad-\frac32+\frac{\sqrt3}{2}i,\quad-\frac32-\frac{\sqrt3}{2}i.}
$$
The <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 $\mathbf1_{n\equiv d\ (3)}=\frac13\sum_{j=0}^2\omega^{j(n-d)}$ and $E(s^{N_t})=e^{t(s-1)}$ therefore give, for $d=(y-x)\bmod3$,
$$
\boxed{p_{xy}(t)=\frac13\sum_{j=0}^2e^{t(\omega^j-1)}\omega^{-jd}
=\frac13\left[1+2e^{-3t/2}\cos\left(\frac{\sqrt3t}{2}-\frac{2\pi d}{3}\right)\right].}
$$
These are also the entries of $e^{tQ}$ obtained by diagonalizing $Q$. In particular,
$$
\boxed{P(N_t\equiv i\pmod3)=\frac13\left[1+2e^{-3t/2}\cos\left(\frac{\sqrt3t}{2}-\frac{2\pi i}{3}\right)\right],\quad i=0,1,2.}
$$
Back to article page
