Let $X$ be a Markov chain with transition matrix: $$\mathbf{P}=\begin{pmatrix} 0 & \frac{3}{5} & \frac{2}{5} \\ \frac{3}{4} & 0 & \frac{1}{4} \\ \frac{2}{3} & \frac{1}{3} & 0\end{pmatrix}\;\;\text{and initial distribution}\;\pi=\tfrac{1}{12}(5,4,3)$$ Let $\tau (i,j)=\inf \big\{n:\;\{i,j\}\,\text{is a subsequence of}\, \{X_0,\dots,X_n\}\big\}$. I am trying to:
- show $\mathbb{E}[\tau(1,2)]=\mathbb{E}[\tau(2,1)]$
- show $\mathbb{E}_1[T_2]-\mathbb{E}_2[T_1]=\sum_i \pi_i\left(\mathbb{E}_i[T_1]-\mathbb{E}_i[T_2]\right)$
(where $T_k=\inf \{m\geqslant 1:\;X_m=k\}$ is the first passage time at $k$)
So far I have shown that $\mathbf{P},\pi$ are in detailed balance, so the chain is reversible, and hence the distribution of $\{X_0,\dots,X_n\}$is the same as that of $\{X_n,\dots, X_0\}$. So some sort of symmetry argument might be used to prove the first part, but I am not sure how.
For the second part, the RHS are conditioned expectations, so we can write it as $\mathbb{E}[T_1]-\mathbb{E}[T_2]$. Again I think I'm missing something relatively basic but I cannot see why this is the same as $\mathbb{E}_1[T_2]-\mathbb{E}_2[T_1]$.
It would be really helpful if someone could give me a nudge...
Consider the following extension of $\tau(1,2)$: At time $\tau(1,2)$, choose a target state at random (with distribution $\pi$, independent of what has gone before) and continue until the first time that state is hit. The mean time for this total trip is $\Bbb E[\tau(1,2)]+\sum_j \Bbb E_2[D_j]\pi_j=\Bbb E[\tau(1,2)]+K$. Here $D_j:=\inf\{n\ge 0: X_n=j\}$, and $K:=\sum_{j}\Bbb E_i[D_j]\pi_j$ is Kemeny's Constant, and does not depend on the state $i$. Running this trip in reverse (which does not change its expected value) corresponds to starting with distribution $\pi$, running until time $\tau(2,1)$, and then picking a target with law $\pi$ independently of what has gone before, and then stopping when that target is hit. This reverse trip has meanvalue $\Bbb E[\tau(2,1)]+K$ by the previous reasoning and reversibility. It follows that $\Bbb E[\tau(1,2)]=\Bbb E[\tau(2,,1)]$.
The second assertion should follow by subtraction because $\tau(1,2)=D_1+T_2\circ\theta_{D_1}$ and $\tau(2,1)=D_2+T_1\circ\theta_{D_2}$. (Here $\theta_n$ is the time shift operator on path space of the Markov chain.) Thus $$ \Bbb E[D_1]+\Bbb E_1[T_2]=\Bbb E[D_2]+\Bbb E_2[T_1]. $$