What is the probability of being in state 4 after two steps, given that one is in state 5 after 8 steps?
Markov Chain is at top of link. The sample solution is part (f). I have no idea what the summation means (e.g. p77p44p66p55) or why it was given, or the powers of x. I understand why I am finding p(state 4 after 2 steps | state 5 after 8 steps), but am lost otherwise. Any clarification on how I should read those summations and what they mean would be greatly appreciated!
To be in state 5 after eight steps starting from state 0, you must go from state 0 to state 7, from state 7 to state 4, from state 4 to state 6, from state 6 to state 5, and spend another four steps going from states to the same states.
You need to sum the probabilities of the different patterns of steps which will make you be in state 5 after eight steps starting from state 0. Each pattern's probability is the product of the probabilities of its individual steps.
You can ignore going from state 0 to state 0 as this has probability 0.
So the probability of being in state 5 after eight steps starting from state 0 is the sum of the probabilities of the different patterns. The probabilities of the steps which change state appear in each pattern, so you can take these outside the summation, since they all have a common factor of $p_{07}p_{74}p_{46}p_{65}$ or $0.5 \times 0.4 \times 0.8 \times 0.3$, which needs to be multiplied by a sum over the probabilities of going from states to the same states.
That sum is expressed as $\sum p_{77}^i p_{44}^j p_{66}^k p_{55}^l$ or $\sum 0.4^i\times 0.2^j\times 0.7^k\times 1.0^l$ provided that $i+j+k+l=4$ since you need to waste four steps doing this; you also need $i,j,k,l$ to be non-negative integers.
If you want to be in state 4 after two steps and in state 5 after 8 steps, starting from state 0, then the calculation is the same with the additional condition that $i=0$ since you cannot waste any steps going from state 7 to itself.