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...
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$.