I have a Markov chain with state space $E = \{1,2,3,4,5\}$ and transition matrix below:
$$ \begin{bmatrix} 1/2 & 0 & 1/2 & 0 & 0 \\\ 1/3 & 2/3 & 0 & 0 & 0 \\\ 0 & 1/4 & 1/4 & 1/4 & 1/4 \\\ 0 & 0 & 0 & 3/4 & 1/4 \\\ 0 & 0 & 0 & 1/5 & 4/5\ \end{bmatrix} $$
How would I find the conditional probabilities of $\mathbb{P}(X_2 = 5 | X_0 =1)$ and $\mathbb{P}(X_3 = 1 | X_0 =1)$?
I am trying to use the formula (or any other formula, if anyone knows of any) $p_{ij}^{(n)} = \mathbb{P}(X_n = j | X_0 =i)$, the probability of going from state $i$ to state $j$ in $n$ steps.
So $\mathbb{P}(X_2 = 5 | X_0 =1) = p_{15}^2$, so I read the entry in $p_{15}$, and get the answer is $0^2$, but the answer in my notes say it is $1/8$?
Also, I get for $\mathbb{P}(X_3 = 1 | X_0 =1) = p_{11}^3 = (\frac{1}{2})^3 = 1/8$, but the answer says it is $1/6$?
Best Answer
The notation $p^{(2)}_{15}$ is not to be confused with the square of $p_{15}$ since it stands for the $(1,5)$ entry of the square of the transition matrix. Thus, $$ p^{(2)}_{15}=\sum_{i=1}^5p_{1i}p_{i5}. $$ Likewise for $p^{(3)}_{11}$, which is the $(1,1)$ entry of the cube of the transition matrix, that is, $$ p^{(3)}_{11}=\sum_{i=1}^5\sum_{j=1}^5p_{1i}p_{ij}p_{j1}. $$ In the present case, there are only two ways to start from $1$ and to be back at $1$ after three steps, either the path $1\to1\to1\to1$, or the path $1\to3\to2\to1$. The first path has probability $\left(\frac12\right)^3=\frac18$ and the second path has probability $\frac12\frac14\frac13=\frac1{24}$, hence $p^{(3)}_{11}=\frac18+\frac1{24}=\frac16$.