1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
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