# Markov chain - transition matrix - expected value

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

$$k(0)=1+0.25k(0)+0.5k(1)+0.25k(2)$$

Same procedure for the other two states:

$$k(1)=1+0.5k(0)+0.25k(1)+0.25k(2)$$

$$k(2)=1+0.5k(0)+0.25k(1)+0.25k(2)$$

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?

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

Remarks:

• 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".
• 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)$$ ? Commented Feb 23, 2018 at 17:33
• @cnmesr That's right.
– Ian
Commented Feb 23, 2018 at 17:34
• 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? :) Commented Feb 23, 2018 at 17:43