Selected Answers to Problem Set 8
1. Consider section C as the state outside either sections A or B. That is, students transfer into section C, but cannot transfer back. 5/12 of the students in section A remain in section A, while 1/2 of those in section B stay.| 5/12 1/6 0 | A = | 1/6 1/2 0 | | 1/4 1/3 1 |A high power of A can be found in Maple. What should be apparent is that as k approaches infinity:| 0 0 0 | Ak = | 0 0 0 | | 1 1 1 |In order to satisfy AP = P, we must solve for P. Remember that the identity matrix multiplied by any vector yields that vector.AP - P = 0 AP - IP = 0 (A - I)P = 0 | -7/12 1/6 0 | | a | | 1/6 -1/2 0 | | b | = 0 | 1/4 1/3 0 | | c |The unknowns a and b cannot be solved linearly and therefore must be equal to zero.
As for c, since a + b + c = 1 (probability vector), c = 1.
2. The product of two Markov matrices is also a Markov matrix.
A proof can be found here in pdf format.On a side note, this file was created with LaTeX, an incredible powerful and elegant document markup language (this is for documents what HTML is for the web). If you are going into any scientific field, familiarity with Tex and LaTeX, a flavor of TeX, is a huge bonus. There is a learning curve, just as there was with HTML, although much larger. Let this not deter you from learning LaTeX. You can view the source of this document here. Save the .tex file to your hard drive and open it with notepad.
For the second part of the problem, the claim in not valid. Let A be any Markov matrix, while B is a Markov matrix with positive elements. Let the top row of A be filled with zeroes. Therefore, in AB, the cell in the upper-left corner will be equal to zero. If A is positivel, then AB will always be positive (if A, B are markov). However, if only B is positive, then this claim does not hold.
3. If the rat does not leave room one and thus does not enter any other room from room one, then the Markov matrix looks as follows:| 1 1/3 0 1/3 1/4 | | 0 0 1/3 0 1/4 | | 0 1/3 0 1/3 1/4 | | 0 0 1/3 0 1/4 | | 0 1/3 1/3 1/3 0 |This matrix, taken to a high power, yields [1 0 0 0 0], meaning that the rat will, after many turns, be in the first room. This result should not surprise you, since the rat can't leave room one.
4. If the rat starts in room 2, then he has a 30% chance of moving to room 1. The rat has a 100% chance of staying in room 1, meaning he won't move. The matrix looks as follows:| 1.0 0.3 | | 0.0 0.7 |The rat has a 100% chance of staying for at least one hour. To stay for exactly one hour, he must leave the first chance he gets, which is a 30% chance. To stay for exactly two hours, he must leave the second chance he gets, which is 70% * 30%, or 21%. For three hours, the probability is (0.72)(0.3), or 14.7%. This can be formalized as P(n hours) = (0.7n-1)(0.3). To find the expected value as n approches infinity, we need to have a discrete formulation up to infinity (36 hours should suffice for a good approximation, since 0.735*0.3 = 0.00000114. Multiply this by 36 hours and we get about 1/7 of a second). In Maple, we can take the sum as from n=1 to 24 of 0.7n-1*0.3*n to get approximately 3.33 hoursIn the second example, we want to find the number of hours in which the rat is likely to enter the first room. This probability should be above some given threshold, like 50%, 75%, or 90%. The probability that the rat will not enter room one after one hour is 0.70. So the probability to move into room one is 1 - 0.70, or 0.30. After three hours (since the rat moves to room three, then after one hour moves back to room one) the probability to not move into room one is 0.70*0.70, or 0.49. Moving into room one, then, happens at three hours 51% of the time. It breaks this 75% barrier that we hypothetically set after four moves into room two, or at seven hours. At 13 hours, the rat is more than 90% likely to be in room one. If you said that the rat has a 50-50 chance of moving into rooms one or three, then your data will be different; the rat is 50% likely to be in room one at the first move after one hour, 75% likely at three hours, and over 90% likely after seven hours.
5. If we are to find the converging state, then yk+1 = yk and zk+1 = zk. We also know that y + z = 5, since y0 = 0 and z0 = 5. Therefore:y = 0.8y + 0.3z z = 0.2y + 0.7z 0 = -0.2y + 0.3z 0 = 0.2y - 0.3z Solve for y and z: 0.6z = 0.4y z = (2/3)y y + z = 5 y + (2/3)y = 5 5y = 15 y = 3 --> 3 + z = 5 z = 2If B = SDS-1, then B2 = SDS-1SDS-1. Since S-1S = I (inverse relation) then SDS-1SDS-1 = SDIDS-1 = SD2S-1. B3 then equals SD2S-1SDS-1 = SD3S-1. For any k, it follows that Bk = SDkS-1.
6. The answer can be found here in Maple format or PDF format.