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