Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Powers of Markov transition matrices

  1. Jun 26, 2011 #1
    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 = [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)

    3. 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
  2. jcsd
  3. Jun 27, 2011 #2


    User Avatar
    Homework Helper

    i think your first step isn't quite right

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

    then generalise to [tex] s^{(n)} [/tex]

    this should be pretty easy to wirte in index form
    Last edited: Jun 27, 2011
  4. Jun 27, 2011 #3


    User Avatar
    Homework Helper

    Also do you know the einstein index notation short cut?

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

    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
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook