The Student Room Group

Markov Chains

Need a bit of help with how this Markov chain calculation works out.

On state space S = {1,2,3,4,5}, with transition probability matrix P and 2-step transition probability matrix P^2.

Initial probability distribution is P(X0=1) = 1 and P(X0=i) = 0 for i=2,3,4,5.

Question is asking for find P(X3=5) and P(X4=5), and in the answers is states that, for P(X3=5),

P(X3=5)=k=15p1kpk5(2)P(X_3=5) = \displaystyle\sum_{k=1}^{5} p_{1k} p_{k5}^{(2)}

however for P(X4=5),

P(X4=5)=k=15p1k(2)pk5(2)P(X_4=5) = \displaystyle\sum_{k=1}^{5} p_{1k}^{(2)} p_{k5}^{(2)}

And I am very confused as to how they managed to get these values, how would you know whether its the 2-step transition matrix you are using or the first? How can you tell? Thank you for any help.
Original post by Blue7195
Need a bit of help with how this Markov chain calculation works out.

On state space S = {1,2,3,4,5}, with transition probability matrix P and 2-step transition probability matrix P^2.

Initial probability distribution is P(X0=1) = 1 and P(X0=i) = 0 for i=2,3,4,5.

Question is asking for find P(X3=5) and P(X4=5), and in the answers is states that, for P(X3=5),

P(X3=5)=k=15p1kpk5(2)P(X_3=5) = \displaystyle\sum_{k=1}^{5} p_{1k} p_{k5}^{(2)}

however for P(X4=5),

P(X4=5)=k=15p1k(2)pk5(2)P(X_4=5) = \displaystyle\sum_{k=1}^{5} p_{1k}^{(2)} p_{k5}^{(2)}

And I am very confused as to how they managed to get these values, how would you know whether its the 2-step transition matrix you are using or the first? How can you tell? Thank you for any help.


I'm only just studying Markov chains myself, but it may be because 3 is an odd amount of steps so you can only use the one step matrix then the two step, whereas with 4 you can go in two steps and then another two steps as it's even.
Original post by Blue7195
Need a bit of help with how this Markov chain calculation works out.

On state space S = {1,2,3,4,5}, with transition probability matrix P and 2-step transition probability matrix P^2.

Initial probability distribution is P(X0=1) = 1 and P(X0=i) = 0 for i=2,3,4,5.

Question is asking for find P(X3=5) and P(X4=5), and in the answers is states that, for P(X3=5),

P(X3=5)=k=15p1kpk5(2)P(X_3=5) = \displaystyle\sum_{k=1}^{5} p_{1k} p_{k5}^{(2)}

however for P(X4=5),

P(X4=5)=k=15p1k(2)pk5(2)P(X_4=5) = \displaystyle\sum_{k=1}^{5} p_{1k}^{(2)} p_{k5}^{(2)}

And I am very confused as to how they managed to get these values, how would you know whether its the 2-step transition matrix you are using or the first? How can you tell? Thank you for any help.


@SeanFM is basically spot on here, but let me just add a bit. The Markov property of a Markov chain means that the transition matrix P(n)P^{(n)} of a multi-step transition XiXi+n X_i \rightarrow X_{i+n} is simply given by a power:

P(n)=Pn \displaystyle P^{(n)} = P^n

where PP is the 1-step transition matrix. This immediately means that


P(n)=PaPb \displaystyle P^{(n)} = P^a P^b

wherever a+b=n a + b = n for positive integers a & b. So, unraveling this, it means that if you want to get from state i to state j after n steps in an M state Markov chain you can do it via

k=1MPi,kaPk,jb=k=1MPi,k(a)Pk,j(b)[br] \displaystyle \sum_{k=1}^{M} P_{i, k}^{a} P_{k, j}^b = \sum_{k=1}^{M} P_{i, k}^{(a)} P_{k, j}^{(b)}[br]

for any positive integral a and b that sum to n.
(edited 7 years ago)
Reply 3
Original post by Gregorius
@SeanFM is basically spot on here, but let me just add a bit. The Markov property of a Markov chain means that the transition matrix P(n)P^{(n)} of a multi-step transition XiXi+n X_i \rightarrow X_{i+n} is simply given by a power:

P(n)=Pn \displaystyle P^{(n)} = P^n

where PP is the 1-step transition matrix. This immediately means that


P(n)=PaPb \displaystyle P^{(n)} = P^a P^b

wherever a+b=n a + b = n for positive integers a & b. So, unraveling this, it means that if you want to get from state i to state j after n steps in an M state Markov chain you can do it via

k=1MPi,kaPk,jb=k=1MPi,k(a)Pk,j(b)[br] \displaystyle \sum_{k=1}^{M} P_{i, k}^{a} P_{k, j}^b = \sum_{k=1}^{M} P_{i, k}^{(a)} P_{k, j}^{(b)}[br]

for any positive integral a and b that sum to n.


Thank you so much!

Quick Reply