- #1

cientifiquito

- 7

- 0

## Homework Statement

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 P

^{n}gives the probability that the Markov chain, starting in state s

_{i}, will be in state s

_{j}after n steps.

## Homework Equations

p

^{(2)}

_{ij}= [itex]\sum^{r}_{k=1}[/itex]p

_{ik}p

_{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[itex]^{(n)}_{ij}[/itex] = [itex]\sum^{r}_{k=1}[/itex]p[itex]^{(n-1)}_{ik}[/itex]p[itex]^{(n-1)}_{kj}[/itex]

then p

^{n+1}must be:

p[itex]^{(n+1)}_{ij}[/itex] = [itex]\sum^{r}_{k=1}[/itex]p[itex]^{(n +1 - 1)}_{ik}[/itex]p[itex]^{(n + 1 -1)}_{kj}[/itex]

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