Massachusetts Institute of Technology Department of Electrical Engineering & Computer Science 6.041/6.431: Probabilistic Systems Analysis (Spring 2006) Solutions for Recitation 21 Markov Chains: Absorption Probabilities and Expected Time to Absorption May 11, 2006 1. (a) The Markov chain is shown below. 1/8 9 1/4 1 1/2 3/8 1/8 3/8 1/8 1/8 1/2 1 6-3 6-2 6-1 15 3/8 1/8 By inspection, the states 6-1, 6-2, and 6-3 are all transient, since they each have paths leading to either state 9 or state 15, from which there is no return. Therefore she eventually leaves course 6 with probability 1 . (b) This is simply the absorption probability for the recurrent class consisting of the state course-15. Let us denote the probability of being absorbed by state 15 conditioned on being in state i as ai. Then a15 = 1 a9 = 0 1 1 1 1 1 a6−1 = a6−1 + (1) + a6−2 + (0) + a6−32 8 8 8 8 1 3 1 a6−2 = (1) + a6−1 + a6−32 8 8 1 3 3 a6−3 = (0) + a6−1 + a6−24 8 8 Solving this system of equations yields 105 a6−1 = ≈ 0.571 184 We will keep the other ai’s around as well - they will be useful later: a6−2 = 0.77717 a6−3 = 0.50543 Page 1 of 5Massachusetts Institute of Technology Department of Electrical Engineering & Computer Science 6.041/6.431: Probabilistic Systems Analysis (Spring 2006) (c) This corresponds to an expected time until absorption for the transient state 6 − 1. Let µi be the expected time until absorption conditioned on being in state i. Then µ15 = 0 µ9 = 0 1 1 1 1 1 µ6−1 = 1 + µ6−1 + (0) + µ6−2 + (0) + µ6−32 8 8 8 81 3 1 µ6−2 = 1 + (0) + µ6−1 + µ6−32 8 81 3 3 µ6−3 = 1 + (0) + µ6−1 + µ6−24 8 8Solving this system of equations yields 162 81 µ6−1 = = ≈ 3.522 46 23 (d) The student buys one ice cream cone every time she goes from 6-2 to 6-1 or from 6-3 to 6-1, and buys no more than 2 ice cream cones. Let us denote vi(j) as the probability that she transitions from from 6 − 2 to 6 − 1 or from 6 − 3 to 6 − 1 j times before leaving course 6, conditioned on being in state i. Then we are interested in the expected value of the random variable N , which denotes the number of cones bought before leaving course 6, and takes on the values 0, 1, or 2. So E[N] = (0)v6−1(0) + (1)v6−1(1) + (2)(1 − v6−1(0) − v6−1(1)) We use the total probability theorem, conditioning on the next day, to yield the following set of recursive equations: v15(0) = 1 v9(0) = 1 1 1 1 1 1 v6−1(0) = v6−1(0) + v6−2(0) + v6−3(0) + (1) + (1) 2 8 8 8 83 1 1 v6−2(0) = (0) + v6−3(0) + (1) 8 8 23 3 1 v6−3(0) = (0) + v6−2(0) + (1) 8 8 4 Solving this system of equations yields: 46 v6−1(0) = ≈ 0.754 61 We still need to find v6−1, and we do this by again conditioning on the second following day: 1 1 1 1 1 v6−1(1) = v6−1(1) + v6−2(1) + v6−3(1) + (0) + (0) 2 8 8 8 83 1 1 v6−2(1) = v6−1(0) + v6−3(1) + (0) 8 8 23 3 1 v6−3(1) = v6−1(0) + v6−2(1) + (0) 8 8 4Page 2 of 5Massachusetts Institute of Technology Department of Electrical Engineering & Computer Science 6.041/6.431: Probabilistic Systems Analysis (Spring 2006) Notice in the second and third equations that when she goes into state 6-1, this automatically sets v to 1, so we require that there be no more transitions from 6-2 to 6-1 or from 6-3 to 6-1 after the second day (that is, v=0 starting in state 6-1, whose probability we found before). Solving this system of equations yields: 690 v6−1(1) = ≈ 0.185 3721 Finally, we can solve for the expected number of cones: E[N] = (0)v6−1(0) + (1)v6−1(0) + (2)(1 − v6−1(0) − v6−1(1)) 690 225 = + 2( )3721 37211140 = ≈ 0.306 3721 (e) We want to find the expected time to absorption conditioned on the event that the student eventually ends up in state 15, which we will call A. So Pi,j|A = P(Xn+1 = j|Xn = i, X∞ = 15) P(X∞ = 15|Xn+1 = j)P(Xn+1 = j|Xn = i) = P(X∞ = 15|Xn = i) aj Pi,j = ai where ak is the absorption probability of eventually ending up in state 15 conditioned on being in state k, which we found in part (b). So we may modify our chain with these new conditional probabilities and calculate the expected time to absorption on the new chain. Note that state 9 now disappears. Also, note that Pj,j|A = Pj,j , but Pi,j|A 6= Pi,j for i 6= j, which means that we may not simply renormalize the transition probabilities in a uniform fashion after conditioning on this event. Let us denote the new expected time to absorption, conditioned on being in state i as ˜µi Our system of equations now becomes µ˜15 = 0 a6−1 1 a6−2 1 a6−3 1 µ˜6−1 = 1 + µ˜6−1 + 0 + µ˜6−2 + 0 + µ˜6−3 a6−1 2 a6−1 8 a6−1 8 a6−1 3 a6−3 1 µ˜6−2 = 1 + 0 + µ˜6−1 + µ˜6−3 a6−2 8 a6−2 8 a6−1 3 a6−2 3 µ˜6−3 = 1 + 0 + µ˜6−1 + µ˜6−2 a6−3 8 a6−3 8 Solving this system of equations yields 1763 µ˜6−1 = ≈ 3.65 483 (f) The new Markov chain is shown below. Page 3 of 5Massachusetts Institute of Technology Department of Electrical Engineering & Computer Science 6.041/6.431: Probabilistic Systems Analysis (Spring 2006) 1/4 1 1/2 3/8 6-3 6-2 6-1 9 3/8 1/6 1/6 1/6 3/4 1/4 This is another expected time to absorption question on the new chain. Let us define µk to be the expected number of days it takes the student to go from state k to state 9 in this new Markov chain: 1 1 1 1 µ6−1 = 1 + µ6−1 + µ6−2 + µ6−3 + (0) 2 6 6 63 1 µ6−2 = 1 + µ6−1 + µ6−34 43 3 1 µ6−3 = 1 + µ6−1 + µ6−2 + (0) 8 8 4Solving this system of equations yields: 86 µ6−1 = ≈ 6.615 13 (g) The corresponding Markov chain is the same as the one in part (a) except p9,6−1 = 18 , p9,9 = 7 1 7 , p15,6−1 = , p15,15 = instead of p9,9 = 1, p15,15 = 1. 8 8 8 We can consider state 6-1 as an absorbing state. Let µk be the expected number of transi-tions to be absorbed if we start at state k 1 7 µ9 = + (1 + µ9) ⇒ µ9 = 8 8 81 7 µ15 = + (1 + µ15) ⇒ µ15 = 8 8 83 3 1 µ6−3 = + (1 + µ6−2) + (1 + µ9)8 8 …
View Full Document
Unlocking...