This preview shows page 1 out of 3 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 3 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 3 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Massachusetts Institute of Technology Department of Electrical Engineering & Computer Science 6.041/6.431: Probabilistic Systems Analysis (Fall 2010) Problem Set 8 Due November 15, 2010 1. Oscar goes for a run each morning. When he leaves his house for his run, he is equally likely to go out either the front or back door; and similarly, when he returns, he is equally likely to go to either the front or back door. Oscar owns only five pairs of running shoes which he takes off immediately after the run at whichever door he happens to be. If there are no shoes at the door from which he leaves to go running, he runs barefooted. We are interested in determining the long-term proportion of time that he runs barefooted. (a) Set the scenario up as a Markov chain, specifying the states and transition probabilities. (b) Determine the long-run proportion of time Oscar runs barefooted. 2. Consider a Markov chain X1, X2, . . . modeling a symmetric simple random walk with barriers, as shown below: 1/2 1/2 1/2 1/2 1/21/21/21/21/2 1/2 1/2 1/2 1/2 1/2 0 1 m−1−m (a) Explain why |X1|, |X2|, |X3|, . . . also satisfies the Markov property and draw the associated chain. (b) Suppose that we also wish to keep track of the largest deviation from the origin, i.e., define the largest deviation at time t as Yt = max{|X1|, |X2|, . . . , |Xt|}. Draw a Markov chain that keeps track of the largest deviation and explain why it satisfies the Markov property. 3. As flu season is upon us, we wish to have a Markov chain that models the spread of a flu virus. Assume a population of n individuals. At the beginning of each day, each individual is either infected or susceptible (capable of contracting the flu). Suppose that each pair (i, j), i 6 j, independently comes into contact with one another during the daytime with probability p.= Whenever an infected individual comes into contact with a susceptible individual, he/she infects him/her. In addition, assume that overnight, any individual who has been infected for at least 24 hours will recover with probability 0 < q < 1 and return to being susceptible, independently of everything else (i.e., assume that a newly infected individual will spend at least one restless night battling the flu). (a) Suppose that there are m infected individuals at daybreak. What is the distribution of the number of new infections by day end? (b) Draw a Markov chain with as few states as possible to model the spread of the flu for n = 2. In epidemiology, this is called an SIS (Susceptible-Infected-Susceptible) model. (c) Identify all recurrent states. Due to the nature of the flu virus, individuals almost always develop immunity after contracting the virus. Consequently, we improve our model and assume that individuals become infected at most one time. Thus, we consider individuals as either infected, susceptible, or recovered. Page 1 of 2Massachusetts Institute of Technology Department of Electrical Engineering & Computer Science 6.041/6.431: Probabilistic Systems Analysis (Fall 2010) (d) Draw a Markov chain to model the spread of the flu for n = 2. In epidemiology, this is called an SIR (Susceptible-Infected-Recovered) model. (e) Identify all recurrent states. 4. Consider the Markov chain below. For all parts of this problem, the process is in state 3 imme-diately before the first transition. Be sure to comment on any unusual results. 1/2 4/10 3/4 1/4 1/2 S SS 1 2 3 S 6 S 7 S S4 5 1 1/21/21/2 1/41/4 3/10 1/10 2/10 1 (a) Find the variance for J, the number of transitions up to and including the transition on which the process leaves state 3 for the last time. (b) Find the expectation for K, the numb er of transitions up to and including the transition on which the process enters state 4 for the first time. (c) Find πi for i = 1, 2, . . . , 7, the probability that the process is in state i after 1010 transitions. (d) Given that the process never enters state 4, find the πi’s as defined in part (c). G1† . Consider a Markov chain {Xk} on the state space {1, . . . , n}, and suppose that whenever the state is i, a reward g(i) is obtained. Let Rk be the total reward obtained over the time interval {0, 1, . . . , k}, that is, Rk = g(X0) + g(X1) + · · · + g(Xk). For every state i, let mk(i) = E[Rk | X0 = i], and vk(i) = var(Rk | X0 = i) respectively be the conditional mean and conditional variance of Rk, conditioned on the initial state being i. (a) Find a recursion that, given the values of mk(1), . . . , mk(n), allows the computation of mk+1(1), . . . , mk+1(n). (b) Find a recursion that, given the values of mk(1), . . . , mk(n) and vk(1), . . . , vk(n), allows the computation of vk+1(1), . . . , vk+1(n). Hint: Use the law of total variance. †Required for 6.431; optional for 6.041 Page 2 of 2MIT OpenCourseWarehttp://ocw.mit.edu 6.041 / 6.431 Probabilistic Systems Analysis and Applied ProbabilityFall 2010 For information about citing these materials or our Terms of Use, visit:


View Full Document

MIT 6 041 - Problem Set #8

Documents in this Course
Quiz 1

Quiz 1

5 pages

Quiz 2

Quiz 2

6 pages

Quiz 1

Quiz 1

11 pages

Quiz 2

Quiz 2

2 pages

Syllabus

Syllabus

11 pages

Quiz 2

Quiz 2

7 pages

Quiz 1

Quiz 1

6 pages

Quiz 1

Quiz 1

11 pages

Quiz 2

Quiz 2

13 pages

Quiz 1

Quiz 1

13 pages

Load more
Download Problem Set #8
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Problem Set #8 and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Problem Set #8 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?