Calculating conditional probability for markov chain

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

-

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$.
Thanks Didier! I can get that $p_{15}^{(2)} = 1/6$, but for $p_{11}^{(3)}$ (and for calculations that involve more than 3 steps etc.), is there an easier way to calculate it? – Henry Apr 10 '12 at 23:26
One looks for the paths $1\to u\to v\to 1$ with positive probability. The first column of the matrix shows that $v=1$ or $v=2$. If $v=1$, one cannot leave $1$ and be back on time (smallest loop of length $3$) hence $u=1$. If $v=2$, one must leave $1$ right away, hence $u=3$. Done. – Did Apr 10 '12 at 23:59
I will give not really formal solution, but maybe this will help you too. $P(X_2=5|X_0=1)$ means getting from the state 1, at the moment 0, to the state 5, at the moment 2. So we are allowed to make to make two steps. Final destination - state 5, is column 5, so nonzero probabilities to get there are from states 3,4,5. So the first step must be getting to one of these. Lets check first row - from state 1 we can get only to states 1,3, which leaves us only one way $1\rightarrow 3\rightarrow 5$, with probability $1/2\cdot1/4=1/8$. A bit longer different situation is $P(X_3=1|X_0=1)$, here we have three steps. Thinking in the same way as before there are two ways with probabilities $(1/2)^3$ and $1/3\cdot1/4\cdot1/2$ (sums to $1/6$). Of course Didier's solution is more formal, and it may be worth doing it in this my way only when we have lots of zeros, like in this case (to eliminate possible combinations). This should help you understanding why $p_{15}^2$ doesn't work here - that would mean $1\rightarrow 1\rightarrow 1$, staying in state 1.