Page 1 of ??Massachusetts Institute of Technology Department of Electrical Engineering & Computer Science 6.041/6.431: Probabilistic Systems Analysis (Spring 2006) Problem Set 10 Topics: Poisson, Markov chains Due: May 10th, 2006 1. All ships travel at the same speed through a wide canal. Eastbound ship arrivals at the canal are a Poisson process with an average arrival rate λE ships per day. Westbound sh ips arrive as an independent Poisson process with average arrival rate λW per day. An indicator at a point in the canal is always pointing in the direction of travel of the most recent s hip to pass it. Each ship takes t days to traverse the length of the canal. (a) Given th at the pointer is pointing west: i. What is the probability that the next sh ip to pass it will be westbound? ii. What is the PDF for the remaining time until the pointer changes direction? (b) What is the probability that an eastbound ship will see no westbound ships during its eastward journey through the canal? (c) We begin observing at an arbitrary time. Let V be the time we have to continue observin g until we see the seventh eastbound ship . Determine the PDF for V . 2. (a) Shuttles depart from New York to Boston every hour on the hour. Passengers arrive ac-cording to a Poisson process of rate λ per hour . Find the expected number of passengers on a shuttle. (Ignore issu es of limited seating.) (b) Now suppose that the shuttles are no longer operating on a deterministic schedule, but rather their interdeparture times are independent and exponentially distributed with rate µ per hour. Find the PMF for the number of shuttles arriving in one hour. (c) Let us define an “event” in the airport to be either the arrival of a passenger, or the departure of a plane. With the same assumptions as in (b ) above, find the expected number of “events” that occur in one hour. (d) If a passenger arrives at the gate, and sees 2λ people waiting, find his/her expected time to wait until the next shuttle. (e) Find the PMF for the number of people on a shuttle.†Required for 6.431; optional for 6.041 Page 2 of ??Massachusetts Institute of Technology Department of Electrical Engineering & Computer Science 6.041/6.431: Probabilistic Systems Analysis (Spring 2006) 3. Consider the follow ing Markov chain: 1 1 S 0 1/21/2 1/4 S S S SS 1 2 3 4 5 1/41/2 1/2 1/2 1/3 1/31/3 Given that the above process is in state S0 just before the first trial, determine by inspection the probability that: (a) The process enters S2 for the first time as the result of the kth trial. (b) The process never enters S4. (c) The process enters S2 and then leaves S2 on the next trial. (d) The process enters S1 for the first time on the third trial. (e) The process is in state S3 immediately after the nth trial. 4. (a) Identify the transient, recurrent, and periodic states of the discrete state discrete-transition Markov process described by ⎡ ⎤ 0.5 0 0 0 0.5 0 0 ⎢ 0.3 0.4 0 0 0.2 0.1 0 ⎥ ⎢ ⎥ ⎢ 0 0 0.6 0.2 0 0.2 0 ⎥ ⎢ ⎥ [pij] = ⎢ ⎢ 0 0 0 0.5 0 0 0.5 ⎥ ⎥ ⎢ 0.3 0.4 0 0 0.3 0 0 ⎥ ⎢ ⎥ ⎣ 0 0 0.4 0.6 0 0 0 ⎦ 0 0 0 0.6 0 0 0.4 (b) How many classes are formed by the recurrent states of this process? (c) Evaluate limn→∞ p41(n) and limn→∞ p66(n). 5. O ut of the d doors of my house, suppose that in the beginning k > 0 are unlocked and d − k are locked. Every day, I use exactly one door, and I am equally likely to pick any of the d doors. At the end of the day, I leave the door I used that day locked. (a) Show that the number of unlocked doors at the end of day n, Ln, evolves as the state in a Markov process for n ≥ 1. Write down the transition probabilities pij. (b) List transient and recurrent states. (c) Is there an absorbing state? How does rij(n) behave as n → ∞ ? (d) Now, suppose that each day, if the d oor I pick in the morning is locked, I will leave it unlocked at the end of the day, and if it is initially unlocked, I will leave it locked. Repeat parts (a)-(c) for this strategy.Page 3 of ??Massachusetts Institute of Technology Department of Electrical Engineering & Computer Science 6.041/6.431: Probabilistic Systems Analysis (Spring 2006) (e) My third strategy is to alternate between leaving the door I use locked one day and unlocked the next d ay (regardless of the initial condition of the door.) In this case, does the number of unlocked doors evolve as a Markov chain, why/why not? G1† . Consider a Markov chain {Xk} on th e 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 th e 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. G2† . Th e parking garage at MIT has installed a card operated gate, which, unfortunately, is vulnerable to absent-minded faculty and staff. In particular, in each day a car crashes the gate with probability p, in w hich case a new gate must be installed. Also a gate that has survived for m days must be replaced as a matter of periodic maintenance. What is the steady-state expected frequency of gate
View Full Document
Unlocking...