I'm trying to understand the statement:
The probability in going form state $i$ to state $j$ in $n$ steps is given by $$\left(P^n\right)_{i,j}$$
this is followed by an example for $k=2$ steps:
$$P_{i,1}P_{1,j} + P_{i,2}P_{2,j} + ... + P_{i,n}P_{n,j} = \sum_{k=1}^n P_{i,k}P_{k,j} = \left(P^2\right)_{i,j}$$
to be honest, this doesn't make much sense to me, why does this work? The only way that I'm maybe getting it is by going about it like so:
- take the i,j indices to the outside:
$$P_{i,1}P_{1,j} + P_{i,2}P_{2,j} + ... + P_{i,n}P_{n,j} \tag 1$$
$$=\left(P_{1,1}P_{1,1} + P_{2,2}P_{2,2} + ... + P_{n,n}P_{n,n}\right)_{i,j} \tag 2$$
$$= \left( P_{1,1}^2 + P_{2,2}^2 + ... + P_{n,n}^2 \right)_{i,j} \tag3$$
but I'm unsure that's true, and if it is, how is it that (3) is equal to $\left(P^2\right)_{i,j}$
I believe it’s meant to be interpreted as “take the n^(th) power of P and extract the (i,j)^(th) entry.”
If you’re asking why that’s the proper computation to find the probability of going from i to j in 2 steps, it’s taking into account the possibility of going from i to any state on the first step and then to j on the second step. i.e. Consider every possible state transition/trajectory and average the outcome by weighting appropriately.
You can see this if you write out an arbitrary transition matrix P and square it. The (i,j)^(th) entry should be exactly the sum you’re asking about.