Let $\;M=\begin{pmatrix} 0.25 & 0.5 & 0.25\\ 0.5 & 0.25 & 0.25\\ 0.5 & 0.25 & 0.25 \end{pmatrix}\;$ be the transition matrix of a markov chain with states $S=\left\{0,1,2\right\}$. Calculate the expected value for the amount till state $1$ is reached, if we start from state $2$.

I've created this task myself and I hope it is clear because I couldn't find a real life example or something like that :)

The thing is I write an exam soon and I'm not quite sure if my solution is correct like that?

If we start from state $0$, we will reach state $0$ with a probability of $0.25$, state $1$ we reach with probability $0.5$ and state $2$ with probability $0.25$. Thus we have


Same procedure for the other two states:



Now, all we need to do is to solve this linear system and the result of $k(2)$ is the expected value we were looking for?


1 Answer 1


That is almost correct, except that your linear system does not know which state you want to hit. To "tell" it that, you should set $k(1)=0$.


  • The linear system you wrote down turns out to have no solution. You can prove this using linear algebra: the column space of $A$ is orthogonal to the null space of $A^T$, and the null space of $A^T$ contains constant vectors. You can understand this using probability: your incorrect system describes the expected time for a process that will never terminate to terminate. By inserting the boundary condition, you obtain a system with a solution.
  • If you wanted the average time to return to state 1 from state 1, a slightly different technique is required. Call the desired answer $x$, then $x=1+0.5k(0)+0.25k(2)$, and $k(0)$ and $k(2)$ satisfy the same equations as before, involving $k(1)$ which is still zero.
  • There's a whole class of such tricks used for both computation and theory, falling under the umbrella of "renewal theory".
  • $\begingroup$ Oh thanks, then we have these equations right? $$k(0)=1+0.25k(0)+0.5k(1)+0.25k(2)$$ $$k(1)=0$$ $$k(2)=1+0.5k(0)+0.25k(1)+0.25k(2)$$ Which makes the system a lot easier $$k(0)=1+0.25k(0)+0.25k(2)$$ $$k(1)=0$$ $$k(2)=1+0.5k(0)+0.25k(2)$$ ? $\endgroup$
    – cnmesr
    Commented Feb 23, 2018 at 17:33
  • 1
    $\begingroup$ @cnmesr That's right. $\endgroup$
    – Ian
    Commented Feb 23, 2018 at 17:34
  • 1
    $\begingroup$ You just editted your answer and mentioned "average time". What do we need to do if we want calculate the "average time to return to state $1$ from state $1$". Maybe you can add that if it's not too much? :) $\endgroup$
    – cnmesr
    Commented Feb 23, 2018 at 17:43
  • 1
    $\begingroup$ @cnmesr Added it. $\endgroup$
    – Ian
    Commented Feb 23, 2018 at 19:14
  • $\begingroup$ Great, thank you so much! :)) $\endgroup$
    – cnmesr
    Commented Feb 23, 2018 at 19:31

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .