| Math 210 | Fall 2008 |
|---|
Problem Set 7, Due: Thursday, Nov. 6, 2008
(late papers OK until 1:00 Friday)Because of elections this week, the homework assignment is a bit shorter. Markov Chains
- There is a long long queue to buy tickets for a Red Hot Chilli Peppers concert. Everyone sees the person selling tickets whisper to the first in line that "Yes, there are still some tickets left." She tells the guy behind her and so on down the line.
However, Red Hot Chilli Peppers fans are not reliable transmitters. If one is told "yes", there is only an 80% chance that person will report "yes" to the next person. On the other hand, being optimistic, if one hears "no", there is a 40% chance that fan will report "yes". If the queue is very long, what fraction of them will hear "there are no tickets left"?
- A chemistry course is taught in two sections. Every week 1/4 of those in Section A and 1/3 of those in section B drop the course and 1/6 of each section transfer to the other section.
a). Find the 3 by 3 transition matrix A describing this.
b). Compute A2, A10, A50, and A100 and state what your results say about the limiting distribution of students.
c). Find all probability vectors P that satisfy AP = P. What relation does this result have with your work in part b)?
- a) If A is the transition matrices for a Markov chain and V is any vector, show that
(sum of the elements of AV) = (sum of the elements of V).
b). If A and B are both n × n transition matrices for Markov chains, does their product AB also have this property? Proof or counterexample.
c). With A and B as above, if all the elements of A are positive, does this imply that all the elements of AB are positive? Proof or counterexample.
d). With A and B as above, if all the elements of B are positive, does this imply that all the elements of AB are positive? Proof or counterexample
- Redo the "rat in a 5 room maze" problem that we discussed in class (see Markov chains notes) but with the modification that if the rat enters Room 1, it considers it "home" and does not leave since there are many friends and lots of food. Your task is to write the new transition matrix and find the long-term probablity that a rat will be in each room. (The result should not surprise you).
- Say y0 = 0 and z0 = 5, while y1, z1, y2, z2, ... are defined recursively by the rules:
yk+1 = .8 yk + .3zk zk+1 = .2 yk + .7zka). Find the limiting values of yk and zk as k tends to infinity.
b). Say that the matrices B, D, and S satisfy B = SDS-1.
b-i). Show that Bk = SDkS-1.
b-ii). [For those who have had Math 240, 312, 370, or 412.] Let A be the matrix associated with the above equations for yk+1 and zk+1. Find an invertible matrix S and a diagonal matrix D so that A = SDS-1.
b-iii). Apply B-ii) to get formula for Ak in terms of S and Dk.
b-iv). Then use this to find formulas for yk and zk.
- Susan is in jail and has $3. She can get out on bail if she has $8. A guard agrees to make a series of bets with her. If Susan bets $c she wins $c with probability .4 and thus looses $c with probability .6. Find the probability that she wins $8 before loosing all of her money under each of the following strategies:
(a). [Timid Strategy] She bets $1 each time.
(b). [Bold Strategy] Each time she bets as much as possible, but not more than necessary to bring her savings up to $8.
(c). Which of these two strategies give Susan a better chance of getting out of jail?This problem is from Chapter 11 (page 424 #13) of Grinstead & Snell's "Introduction to Probability", available online: Grinstead-Snell Chapter 11, Markov Chains (pdf)
Note that for this particular example, it is possible for you to develop the theory from scratch on your own without using the formulas in this text. But the text is a valuable reference.
NOTE: The Grinstead - Snell book's transition matrices are the TRANSPOSE of ours (there the sum of each ROW is 1) so you will need to make some minor adjustments to change to our class's approach.