Finding the expected number of returns to transient state for a reducible and periodic markov chain.

Question

I am working on a problem that provides the Markov chain as:

"The Markov chain on state space {1,2,3,4,5,6}. From 1 it goes to 2 or 3 equally likely. From 2 it goes back to 2. From 3 it goes to 1, 2, or 4 equally likely. From 4 the chain goes to 5 or 6 equally likely. From 5 it goes to 4 or 6 equally likely. From 6 it goes straight to 5."

I have interpreted this as the transition matrix:

$$ \mathbf{P} = \begin{bmatrix}0&\frac{1}{2}&\frac{1}{2}&0&0&0\\ 0&1&0&0&0&0\\ \frac{1}{3}&\frac{1}{3}&0&\frac{1}{3}&0&0\\ 0&0&0&0&\frac{1}{2}&\frac{1}{2}\\ 0&0&0&\frac{1}{2}&0&\frac{1}{2}\\ 0&0&0&0&1&0\end{bmatrix} $$

The question that is asked is:

If you start the Markov chain at 1, what is the expected number of returns to 1?

I am provided with the additional information: "Observe that from 1 you can go to 2, you can go to 3 then leave to 2 or to 4, or you can go to 3 then return to 1. With the first three moves you will never return to 1."

I have tried to reduce this chain by focusing on the first recurrent class 2. So I have written a reduced transition matrix as $$ \tilde{\mathbf{P}} = \begin{bmatrix} 0 & \frac{1}{2} & \frac{1}{2} \\ 0 & 1 & 0\\ \frac{1}{3} & \frac{2}{3} & 0 \end{bmatrix} $$ with the idea that we $\frac{2}{3}$ chance to leave the transient class at state 3. Am I correct in this thinking?

I know that we can find the expected number of returns to a transient state $i$ by finding the $j,i$ entry of $(\mathbf{I} - \mathbf{Q})^{-1}$ where $\mathbf{Q}$ is the sub matrix consisting of the transient states. The problem here is that I don't know how I can reorganize the rows to allow to us to write

$$ \tilde{\mathbf{P}} = \begin{bmatrix} \mathbf{R}& \mathbf{0}\\ \mathbf{S}& \mathbf{Q} \end{bmatrix} $$ which leads me to believe I either incorrectly wrote the original matrix, or my sub matrix.

I have been stuck at this point, so I am unsure of how to proceed to find the expected number of returns to state 1.

Answer 1

Observe that states $4$, $5$, and $6$ behave as one absorbing state. So rewrite the state space as $\{1,3,\delta\}$ (with $\delta$ considered as states $2$, $4$, $5$, and $6$) and the transition matrix $\hat P$ with the $(i,j)$ entry of $\hat P$ consisting of the sum of transitions from states $1-6$ to state $\delta$: $$ \hat P = \begin{bmatrix} 0&\frac12&\frac12\\ \frac13&0&\frac23\\ 0&0&1 \end{bmatrix}. $$ Here the rows/columns are in order $1,3,\delta$. Now $\hat P$ is of the form $$ \begin{pmatrix} Q&R\\0&I \end{pmatrix} $$ where $Q$ is the substochastic matrix consisting of transitions between transient states, $R$ that consisting of transitions from transient states to the absorbing state, $0$ the $0$ matrix, and $I$ the identity matrix. We can now compute the fundamental matrix $$ N = \sum_{k=0}^\infty Q^k =(I-Q)^{-1} = \begin{bmatrix}1&\frac12\\-\frac13&1 \end{bmatrix}^{-1} = \begin{bmatrix}\frac65&\frac35\\\frac25&\frac65 \end{bmatrix}. $$

So the expected number of times the state is in state $1$, given that it started in state $1$, is $\frac65$ - and the expected number of returns to state $1$ is one less, $\frac15$.

Answer 2

You can certainly try to work with a reduced transition matrix or even the original one, but that kind of misses the point of the hint: If the process is in state 1, then there is a single path along which it can return to that state, and the probability of this happening is $\frac12\cdot\frac13=\frac16$. The number of returns is therefore geometrically distributed, and the expectation of a geometric distribution has a well-known (or easy to compute, if you don’t know it) value.

Working with your approach, rearranging the matrix into the required form is the same thing as relabeling the states, so whenever you swap rows you also need to swap the corresponding columns. In this case, swapping the first two rows and the first two columns will do the trick.