I have a problem with the following task:

A Markov chain has a set of states in this case $S = \{1, 2, 3\}$ with transition matrix \begin{pmatrix} 0 & 1 & 0 \\ 0.5 & 0 & 0.5 \\ 0 & 1 & 0 \\ \end{pmatrix} Initial state in our Markov chain is $S_{1}$. Find mean return time to state $S_{1},S_{2},S_{3}$.

Unfortunately, I have no idea how to calculate the mean return time to state 1, 2 and 3. I've never done problems like that. Can I ask you what should I do to determine mean return times to states 1, 2 and 3?

Thank you very much for help...


1 Answer 1


This is called "first-transition analysis." Let $h\left(i\right)$ be the mean time to reach state $1$ given that you start in state $i$ (you can then repeat this same procedure for the other two target states). Then,

\begin{eqnarray*} h\left(1\right) &=& 0,\\ h\left(2\right) &=& 1 + 0.5h\left(1\right) + 0.5h\left(3\right),\\ h\left(3\right) &=& 1 + h\left(2\right). \end{eqnarray*}

If you are already in state $1$, you have already reached it, so the mean time is zero. If you are in state $2$, you first spend one time unit to transition out of state $2$ (that is the significance of adding $1$ in front). After that you will be in either state $1$ or state $3$, and once you are in either of those, the problem "restarts" with that as your starting state -- since this is a Markov chain, the distribution of the future trajectory depends only on the most recent known history. If the problem restarts in state $3$, the expected time to reach $1$ from that point on will be $h\left(3\right)$ by definition, so you just need to take a weighted average of $h\left(1\right)$ and $h\left(3\right)$ because your next state (the one used to restart the problem) will actually be randomly determined.

The above is a system of linear equations, so you can easily solve it. Now, what you actually want to compute is the mean return time to state $1$ given that you started there. From the transition matrix, this is equal to $1 + h\left(2\right)$, since you spend one time unit to leave state $1$, and after that you will automatically "restart" in state $2$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.