A Markov chain has state space $\{a, b, c\}$ and transition matrix

$$P=\left(\begin{array}{ccc} 0 & 3 / 5 & 2 / 5 \\ 3 / 4 & 0 & 1 / 4 \\ 2 / 3 & 1 / 3 & 0 \end{array}\right)$$

where the rows $1,2,3$ correspond to $a, b, c$, respectively. Show that this Markov chain is equivalent to a random walk on some graph with 6 edges.

Let $k(i, j)$ denote the mean first passage time from $i$ to $j$.

(i) Find $k(a, a)$ and $k(a, b)$.

(ii) Given $X_{0}=a$, find the expected number of steps until the walk first completes a step from $b$ to $c$.

(iii) Suppose the distribution of $X_{0}$ is $\left(\pi_{1}, \pi_{2}, \pi_{3}\right)=(5,4,3) / 12$. Let $\tau(a, b)$ be the least $m$ such that $\{a, b\}$ appears as a subsequence of $\left\{X_{0}, X_{1}, \ldots, X_{m}\right\}$. By comparing the distributions of $\left\{X_{0}, X_{1}, \ldots, X_{m}\right\}$ and $\left\{X_{m}, \ldots, X_{1}, X_{0}\right\}$ show that $E \tau(a, b)=E \tau(b, a)$ and that

$$k(b, a)-k(a, b)=\sum_{i \in\{a, b, c\}} \pi_{i}[k(i, a)-k(i, b)]$$