# Homework Help: Powers of Markov transition matrices

1. Jun 26, 2011

### cientifiquito

1. The problem statement, all variables and given/known data

Prove the following theorem by induction:
Let P be the transition matrix of a Markov chain. The ijth entry p(n)ij of the matrix Pn gives the probability that the Markov chain, starting in state si, will be in state sj after n steps.

2. Relevant equations

p(2)ij = $\sum^{r}_{k=1}$pikpkj
(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)

3. The attempt at a solution

assume that

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

then pn+1 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

2. Jun 27, 2011

### 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

Last edited: Jun 27, 2011
3. Jun 27, 2011

### 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

Last edited: Jun 27, 2011