Massachusetts Institute of TechnologyDepartment of Electrical Engineering & Computer Science6.041/6.431: Probabilistic Systems Analysis(Fall 2008)Problem Set 9Due: November 19, 2008Topics: Markov Chains. [Text sections: 7.1-7.4]1. Consider the discrete state, discrete trial Markov process shown below:In this problem, we will call transitions 1 → 2, 2 → 3, 3 → 1 clockwise transitions. Similarly, wewill classify transitions 3 → 2, 2 → 1, 1 → 3 as counterclockwise transitions. We start observingthe process after a very large number of trials after it begins.(a) Either calculate the steady state probabilities or explain why they do not exist.(b) What is the probability there is a clockwise transition on the first trial we observe?(c) What is the probability there is a counterclockwise transition on the first trial we observe?(d) What is the probability there is a clockwise transition on the first change of state we observe?(e) What is the probability there is a counterclockwise transition on the first change of statewe observe?(f) What is the conditional probability the process was in state 1 when we began observing thesystem, given a clockwise transition occurred on the first trial we observed?(g) What is the conditional probability the process was in state 1 when we began observing thesystem, given a clockwise transition occurred on the first change of state we observed?2. The outcomes of successive flips of a particular coin are dependent and are found to be describedfully by the conditional probabilitiesP (Hn+1|Hn) = 3/4 P (Tn+1|Tn) = 2/3Page 1 of 3Massachusetts Institute of TechnologyDepartment of Electrical Engineering & Computer Science6.041/6.431: Probabilistic Systems Analysis(Fall 2008)where we have used the notation: Event Hk: Heads on kth toss; Event Tk: Tails on kth toss. Weknow that the first toss came up heads.(a) Determine the probability that the first tail will occur on the kth toss(k = 2, 3, 4, . . .).For parts (b) to (d), assume 5000 is a sufficiently large number for the probability of being inany particular state to approximate the steady state probabilities.(b) What is the probability that flip 5000 will come up heads?(c) What is the probability that flip 5000 will come up heads and flip 5002 will also come upheads?(d) Given that flips 5001, 5002, . . . , 5000 + m all have the same result, what is the probabilitythat all of these m outcomes are heads? Simplify your answer as much as possible, andinterpret your result for large values of m.(e) We are told that the 375th head just occurred on the 500th toss. Determine the expectedvalue of the number of additional flips required until we observe the 379th head.3. Josephina is currently a 6-1 student. On each day that she is a 6-1 student, she has a probabilityof 1/2 of being a course 6-1 student the next day. Otherwise, she has an equally likely chance ofbecoming a 6-2 student, a 6-3 student, a c ourse 9 student or a course 15 student the next day. Onany day she is a 6-3 student, she has a probability of 1/4 of switching to course 9, a probabilityof 3/8 of switching to 6-1 and a probability of 3/8 of switching to 6-2 the next day. On any dayshe is a 6-2 s tudent, she has a probability of 1/2 of switching to course 15, a probability of 3/8of switching to 6-1 and a probability of 1/8 of switching to 6-3 the next day.In answering the questions below, assume Josephina will be a student forever. Also assume, thatif Josephina switches to course 9 or course 15, she will stay there and will not change her courseagain.(a) What is the probability that she eventually will leave c ourse 6?(b) What is the probability that she will eventually be in course 15?(c) What is the expected number of days until she leaves course 6?(d) Every time she switches into 6-1 from 6-2 or 6-3, she buys herself an ice cream cone atTosci’s. She can only afford so much ice cream, so after she’s eaten 2 ice cream cones, shestops buying herself ice cream. What is the expected number of ice cream cones she buysherself before she leaves course 6?4. The term diffusion is used to des cribe the thermal motion of a randomly perturbed particle orcollection of particles when there is no average motion in any direction. The gradual spread ofa drop of ink in a bowl of still water is one example. The average time required for a physicalparticle to diffuse a distance x (in any direction) grows quadratically with distance as x2/D ,where D is the “diffusion coefficient” for that type of particle in that medium.The Markov chain depicted, where (p ≤ 1/2), is a simple 1-dimensional model for diffusion of aparticle in air or water from the center to the ends of a long, thin pipe.Page 2 of 3Massachusetts Institute of TechnologyDepartment of Electrical Engineering & Computer Science6.041/6.431: Probabilistic Systems Analysis(Fall 2008)(a) For the following values of n, find the expected time for a particle starting at the origin(state 0) to first reach the state n or −n in the Markov chain.i. For n = 1.ii. For n = 2.iii. For an arbitrary n > 0. [Hint: Use the symmetry of the Markov chain to simplify theproblem.](b) What is the “diffusion coefficient”, D, for this system in terms of the probability p?G1†. Consider a Markov chain {Xk} on the state space {1, . . . , n}, and suppose that whenever thestate is i, a reward g(i) is obtained. Let Rkbe the total reward obtained over the time interval{0, 1, . . . , k}, that is, Rk= g(X0) + g(X1) + · · · + g(Xk). For every state i, letmk(i) = E[Rk| X0= i],andvk(i) = var(Rk| X0= i)respectively be the conditional mean and conditional variance of Rk, conditioned on the initialstate being i.(a) Find a recursion that, given the values of mk(1), . . . , mk(n), allows the computation ofmk+1(1), . . . , mk+1(n).(b) Find a recursion that, given the values of mk(1), . . . , mk(n) and vk(1), . . . , vk(n), allows thecomputation of vk+1(1), . . . , vk+1(n). Hint: Use the law of total variance.†Required for 6.431; optional for 6.041 Page 3 of
View Full Document
Unlocking...