48 FINITE MARKOV CHAINS1.6.2. expected time. Today I did a more thorough explanation of theexpected time until we reach a recurrent state. I started by reviewingthe basics of substochastic matrices.Definition 1.20. A substochastic matrix is a square matrix Q withnonnegative entries so that every row adds up to at most 1.For example,Q =!1/2 1/31/4 3/4"is substochastic.Given any subset C of the set of states S, the C-to-C transitionmatrix will always be substochastic.Lemma 1.21. If C contains no recurrent class thena) I + Q + Q2+ Q3+ · · · converses to (I − Q)−1.b) I + 2Q + 3Q2+ 4Q3+ · · · converges to (I − Q)−2.Proof. (a) follows from the computation(I − Q)(I + Q + Q2+ Q3+ · · · ) = I.For (b), the argument is:(I − Q)(I + 2Q + 3Q2+ 4Q3+ · · · ) == I + 2Q + 3Q2+ 4Q3+ · · ·−Q − 2Q2− 3Q3− · · ·= I + Q + Q2+ Q3· · · = (I − Q)−1by (a). Therefore,I + 2Q + 3Q2+ 4Q3+ · · · =(I − Q)−1I − Q= (I − Q)−2!I gave another example to illustrate both of these formulas.MATH 56A SPRING 2008 STOCHASTIC PROCESSES 49In this example, there is only one recurrent class R1= {2, 3, 4}. Theset C = {1, 2} contains the recurrent state 2 but it does not containa recurrent class (R1is not contained in C). Therefore, the lemmaapplies.Inserting the implied loop at vertex 2, we saw that the substochasticmatrix isQ =!0 3/40 1/2"ThenI − Q =!1 −3/40 1/2"So,(I − Q)−1=!1 3/20 2", (I − Q)−2=!1 9/20 4".These numbers are used to answer questions such as the following.Question 1: If you start at 1, what is the probability that you reach4 before you reach 3?The first step in answering this question is to realize that: It doesnot matter what happens after you reach 3 or 4 because, at that point,the question has been answered. So, the numbersp(3, 2) = 1/3, p(4, 3) = 1/2are irrelevant and we can replace them with 0. In other words, we canmake 3 and 4 into absorbing states. This simplification proces s gives anew probability transition matrix which we put into canonical form:˜P =3 4 1 234121 0 0 00 1 0 01/4 0 0 3/41/4 1/4 0 1/2S1S2QS1is the C-to-3 transition matrix and S2is the C-to-4 transition ma-trix. We also need their total:ST= S1+ S2=!1/41/2".Answer: The answer to the question is given by the first coordinate ofthe vector(I − Q)−1S1=!1 3/20 2"!1/41/4"=!14+3824"=!5/81/2"50 FINITE MARKOV CHAINSwhich is 5/8. (If we started at state 2, the answer would be the secondcoordinate which is 1/2.) This was proved on Monday (Theorem 1.18).The matrix (I − Q)−2is used to answer a different question.Question 2: If we start at X0= 1, how long will it take to reach 3 or4? In other words, we want to calculate the conditional expected valueE(T | X0= 1) =?ofT := smallest n so that Xn= 3 or 4.Answer: Just take the definition of expected value:E(T | X0= 1) :=∞)n=0nP(T = n | X0= 1).ButP(T = n | X0= 1) = (Qn−1ST)1is the first coordinate ofQn−1STbecause T = n means we stay in the set C for n − 1 turns and then goto one of the recurrent states 3, 4 (according to the modified transitionmatrix˜P ). Qn−1gives the probability of stay in C for n − 1 turns andSTgives the probability of moving on the nth turn from C to 3 or 4.E(T | X0= 1) :=∞)n=0nP(T = n | X0= 1)=∞)n=0n(Qn−1* +, -(I−Q)−2ST)1=.(I − Q)−2ST/1=!1 9/20 4"!1/41/2"=!5/22"So, the answer isE(T | X0= 1) =
View Full Document
Unlocking...