0

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:

  1. 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}$

atomsmasher
  • 324

1 Answers1

1

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.

H. Pecoraro
  • 48