Powers of Markov transition matrices

[cientifiquito]

Homework Statement

Prove the following theorem by induction:
Let P be the transition matrix of a Markov chain. The ijth entry p⁽ⁿ⁾_ij of the matrix Pⁿ gives the probability that the Markov chain, starting in state s_i, will be in state s_j after n steps.

Homework Equations

p⁽²⁾_ij = \sum^{r}_{k=1}p_ikp_kj
(where r is the number of states in the Markov chain and P is the square matrix with ik being the probability of transitioning from i to j)

The Attempt at a Solution

assume that

p^{(n)}_{ij} = \sum^{r}_{k=1}p^{(n-1)}_{ik}p^{(n-1)}_{kj}

then pⁿ⁺¹ must be:
p^{(n+1)}_{ij} = \sum^{r}_{k=1}p^{(n +1 - 1)}_{ik}p^{(n + 1 -1)}_{kj}

that's all I've come up with but it doesn't convince me very much

 

[lanedance]

i think your first step isn't quite right

so say P is your transition matrix and s^{(n)} is your state vector at time n, the ith element is the probability of being in state i:
s^{(1)} = s^{(0)}P
s^{(2)} = s^{(1)}P= s^{(1)}P = s^{(0)}PP= s^{(0)}P^2
s^{(3)} = s^{(2)}P= s^{(1)}PP = s^{(0)}PPP= s^{(0)}P^3

then generalise to s^{(n)}

this should be pretty easy to wirte in index form

 

[lanedance]

Also do you know the einstein index notation short cut?

repeated indicies in a product are summed over, saves a bit of time
p_{ij}p_{jk} = \sum_j p_{ij} p_{jk}

And one more, just be a bit careful with you index representation, generally P is not a symmetric matrix (may want to check this) so writing the product PP needs a bit of thought, though i think you've got it right