HW problem 5.7 Math 504. Spring 2008. CSUF
by Nasser Abbasi
Problems
Part(A)
Let be an indicator variable defined as Hence Now we see that Now, let be entry in matrix where , then the above can be written as Which is the same as writing When , then otherwise it is . Hence Let the set of transient states be , and using chapman-kolmogorov, the above can be written as But is multiplying the row of the matrix by the column of the matrix. which is the entry of the matrix , and is multiplying the row of the matrix we just obtained, by the column of the matrix, which is the entry of the matrix . Continue this way, we obtain that is the entry in matrix and so on.
Hence we see that is the entry of a matrix resulting from QED.
Part(B) From part(A), we obtained that is the entry in the matrix resulting from the sum . Since this is a matrix, then we know its elements will all go to zero an gets very large, so this is a convergent sum, hence . Therefore
Part(A) I solve this part in 2 ways, first by conditioning on next state, as required, and then by the counting method explained in the lecture.
by conditioning on next state. Let be the set of all states. Then But by Markov property, chain state on next step depends only on current state. Hence and also since then (1) can be written as Now, when , then since chain already in state after one step. Therefore (2) can be rewritten as But is the same as writing , so the above becomes Using the notation shown in the problem, the above becomes QED.
If we wait for the chain to arrive at its steady state (i.e. we the chain probability state vector does not change, or ), then we observe the chain from that point on, for a long period of time, say . The number of times the chain will be in state during this time is then given by , since is the probability of the chain being in state . So, to find the average number of time units (steps) it took for the chain for go from state back to state we need to divide by the number of times the chain was in state during this time, which we just found as
Hence
Intuitively this makes sense. Since the smaller the probability that the chain will be in state we would expect the time between the events that the chain is in state to become larger, So the relation should be an inverse one, as was found. QED