- #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 Pn gives the probability that the Markov chain, starting in state si, will be in state sj after n steps.
Homework Equations
p(2)ij = [itex]\sum^{r}_{k=1}[/itex]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)
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 pn+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