[Math] Markov chain – transition matrix – expected value

discrete mathematicsmarkov chainsprobabilityprobability theorystatistics

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?

Best Answer

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".
Related Question