MATH 56A SPRING 2008 STOCHASTIC PROCESSES 451.6. The substochastic matrix Q. On Monday, I used the Mouse-Cat-Cheese problem to explain the use of the matrix Q. On Wednesday,I explained this further and applied it to the Leontief model.1.6.1. mouse-cat-cheese. Here is the diagram for the problem (frompage 26 with 4,5 switched).21••121313131212•312•5•4The recurrent classes are the absorbing states: R1= {4}, R2= {5}.In canonical form, we put these first:4 5 1 2 3451231 0 0 0 00 1 0 0 01/2 0 0 1/2 00 0 1/2 0 1/21/3 1/3 0 1/3 0S1S2QThe transient-to-transient matrix is called Q. This will be a squarematrix whose rows add up to ≤ 1.Now we want to calculate the probability that the mouse will beeaten by the cat if he starts in rooms 1,2,3. We get three numberst1, t2, t3:ti:= P(X∞= 4 | X0= i)which form a column vector t. The theorem is:Theorem 1.18. The probability of ending in the first recurrent stateR1is the vector−→t =t1t2t3= (I − Q)−1S1.Proof. We need to consider how long the mouse is going to be movingaround in the transient class T1= {1, 2, 3}. So, let T be the time ittakes for the mouse to reach a recurrent state:T := smallest n so that Xn= 4 or 5.46 FINITE MARKOV CHAINSThen:ti= P(X∞= 4 | X0= i) =∞'n=0P(T = n and Xn= 4 | X0= i).But, the probability that T = n and Xn= 4 given X0= i is the ithcoordinate of the vectorQn−1S1.The reason is that, in order to get to a recurrent class at time T = n,the mouse needs to move around in the transient states for exactlyn − 1 turns. This is given by the matrix Qn−1. Then S1gives theprobability of moving to the recurrent class 4. The product Qn−1S1gives the probability of doing one then the other. This is a columnvector where the row number indicates the starting point.For example,QS1=1 1/2 01/2 0 1/20 1/3 01/201/3=1/25/120.The number 5/12 represents the probability of getting from room 2 toroom 4 in exactly two steps:P(T = 2 and X2= 4 | X0= 2) =p(2, 1)p(1, 4) + p(2, 3)p(3, 4) =1212+1213=512Therefore, the vector−→t is the sum of these vectors for all n:−→t = S1+ QS1+ Q2S1+ · · · = (I + Q + Q2+ · · · )S1.This is equal to(I − Q)−1S1by the following lemma. !Lemma 1.19. The matrix I − Q is invertible and its inverse is givenby(I − Q)−1= I + Q + Q2+ Q3+ · · ·Also, this series converges.Proof. I assumed that the series converges. From this it follows thatthe limit is the inverse of I − Q. The proof is deceptively simple:(I − Q)(I + Q + Q2+ Q3+ · · · )= I + Q + Q2+ Q3+ · · ·−Q − Q2− Q3− · · · = I.!MATH 56A SPRING 2008 STOCHASTIC PROCESSES 47Using the formula in the theorem we get:−→t = (I − Q)−1S1=1710 6 36 12 62 4 91/201/3=6/75/74/7.So, e.g., the probability that the mouse will be eaten by the cat if hestarts in room 2 ist2= 5/7.Next, I talked very quickly about the time that it takes the mouseto reach the cat. I explained this better on
View Full Document
Unlocking...