IEOR 6711: Stochastic Models, I: Final Exam Fall 2007, SOLUTION NOTES

1. The GIN Barbershop (20 points) Ioannis Giannakakis, Gisli Ingimundarson and Behzad Nouri have joined together to form the GIN barbershop. The GIN barbershop has room for at most ve customers, with up to three in service and two waiting. Suppose that potential customers arrive according to a Poisson process at a rate of 10 per hour. Suppose that potential arrivals nding the barber shop full, with three customers in service and two other customers waiting, will leave and not aect future arrivals. Suppose that successive service times are independent exponential random variables with mean 12 minutes. Suppose that waiting customers have limited patience, with each waiting customer being willing to wait only an independent random, exponentially distributed, time with mean 12 minutes before starting service; if the customer has not started service by that time, then the customer will abandon, leaving without receiving service. (a) What proportion of time are all three barbers busy in the long run? (b) What is the total rate of customer abandonment in the long run? (c) What proportion of all potential arrivals are served? (d) What is the probability that, starting empty, the third customer arrives before anybody has completed service? (e) What is the probability that, starting empty, the fourth customer arrives and abandons before anybody has completed service? (f) What is the conditional probability that exactly two arrivals occurred in the rst 20 minutes, given that 8 potential arrivals came in the rst hour? This is a CTMC, specically a BD process. This is very similar to the examples in the BD section of the CTMC notes. Specically, this is a M/M/3/2 + M queueing model, with the +M indicating customer abandonment. Part (a): 34/109; part (b); 90/109; part (c): 96/109. Parts (d) and (e) are elementary properties of exponential random variables. Part (d): 1/3; part (e): 1/30. Part (e) was the most dicult part; it caused some problems: You want + + 2 + 3 + 3 .

Part (e) is binomial b(k : n, p) = b(2 : 8, 1/3). Can be deduced by direct calculation or by knowing that conditional distribution of points within [0, t] given n points there for Poisson process are distributed according to independent uniforms. 2. Back and Forth to Campus (30 points) Professor Prhab Hubilliti lives at the bottom of the hill on the corner of 117th Street and Avenue. Going each way - up hill to to teach his class at Columbia or down hill back home - Prhab either runs or walks. Going up the hill, Prhab either walks at 2 miles per hour or runs at 5 miles per hour. Going down the hill, Prhab either walks at 3 miles per hour or runs at 6 miles per hour. In each direction, he always runs the entire way or walks the entire way. Since Prhab often works late into the night, he often gets up late, and has to run up hill to get to 7th

his class. On any given day, Prhab runs up hill with probability 2/3 and walks up hill with probability 1/3. On the other hand, Prab is less likely to run going back home. On any given day, he runs down hill with probability 1/3 and walks down hill with probability 2/3. (a) What is the average speed Prhab goes up the hill to campus? What is the average speed Prhab goes down the hill back home? (b) What is the long-run proportion of Prhabs total travel time going to and from campus that he spends going up hill to campus? (c) What is the long-run proportion of Prhabs total travel time going to and from campus that he spends running up hill to campus? (d) Let (t) be the expected number of times Prhab has gone to campus and back in his rst t units of time spent travelling back and forth between home and work. State and prove the theorem implying that (t)/t converges to a nite limit as t . Part (a) was worded ambiguously, so you could consider dierent interpretations. I wanted average speed 4 each way, but alternatively you could get 20/7 and 4. I did not pay much attention to (a). Parts (b) and (c) are solved by renewal-reward processes. It is important to use the Distance = Rate times Time D = rT (Dirt) formulation. The answers are: part (b): 27/52; part (c): 3/13. Part (d) is the Elementary Renewal Theorem. The proof involves an application of Walds equation and truncated random variables. The argument involves working with lim inf (limit inferior) and lim sup (limit superior). If you do not know enough about these concepts, look into them. 3. a random walk on n integers (30 points) Consider a random walk on the rst n integers, i.e., on the set {1, 2, . . . , n}, where the probability of going from integer i to integer j in a single step is proportional to (i j )2 for each i and j . (a) What structure helps calculate the stationary distribution of this process without directly solving a system of equations (or calculating a matrix inverse)? Give an expression for that stationary distribution? (b) Starting at 1, what is the expected number of steps before the random walk rst is at 1 again when n = 6? (Find the numerical answer.) (c) Starting at 1, indicate how to compute the expected number of steps before rst visiting one of the states 2, 3 or 4, for any xed n 5? (d) Starting in 1, indicate how to compute the probability of eventually visiting 2 before ever visiting either 3 or 4, again for any xed n 5. (e) Describe the approximate behavior of this random walk for very large n (as n ). This is a DTMC. The extra structure is reversibility. The specic problem is an example of a random walk on a weighted graph. Here the integers are the nodes and there is an arc connecting each pair of integers in the set {1, 2, . . . , n}. This random walk on the integers 2

is then a reversible DTMC in steady state. The transition matrix is not doubly stochastic. For part (a), the stationary distribution is j =
n j =1 k:k=j (k

j )2 j )2

k:k=j (k

1 j n.

Part (b): 42/11. For parts (c) and (d) you want to apply the absorbing Markov chain theory for nite-state DTMCs as in the notes on Markov mouse. Part (c): N = (I Q)1 , then sum elements of the proper row of N ; part (d): B = N R. Choose B1,2 . In parts (c) and (d) you could alternatively attack this directly and write the answer as a solution of a system of equations. The approaches are equivalent. The main thing to note for part (e) is that we are letting n , where n is the number of states, not time. For any n, we see that the random walk is more likely to go far away from its initial state at each step. The most distant end point is the most likely destination. The stationary distribution is U shaped. The middle is 1/4 as likely as the end points. 4. Tandem Queues (20 points) Consider two single-server queues in tandem, i.e., in series. Each queue has unlimited waiting room. Customers are served in order of arrival at each queue. Arrivals come to the rst queue according to a Poisson process with rate . All departures from the rst queue go next to the second queue, while all departures from the second queue leave the system. Let the all the service times be mutually independent, and independent of the arrival process. Let the service times at queue i be exponentially distributed with mean 1/i , where 3 < 21 < 2 . Let Qi (t) be the number of customers at queue i, either waiting or being served, at time t. (a) Does there exist a proper limiting steady-state distribution for Q1 (t) as t ? If so, what is it? (b) Does there exist a proper limiting steady-state distribution for the random vector (Q1 (t), Q2 (t)) as t ? If so, what is it? (c) Let D(t) denote the number of departures from the system (equivalently, from queue 2) during the time interval [0, t]. Find
t

lim E [(D(t) D(t s))Q2 (t)]

for s > 0. (d) Give an expression for P (Q1 (t1 ) = 5, Q2 (t1 ) = 4, Q1 (t2 ) = 7, Q2 (t2 ) = 2) for 0 < t1 < t2 , where P (Q1 (0) = i, Q2 (0) = j ) has a known form. Give expressions for all quantities used. This is a classical Jackson queueing network; see the CTMC notes or the Ross book. For (a) and (b), the stability condition is satised: 1 /1 < 1 and 2 /2 < 1, under the stated assumptions. By basic BD theory, the steady-state distribution of queue one is geometric: P (Q1 () = j = (1 1 )j 1. By basic queueing network theory, the steady-state distribution of the vector of two queue lengths has product form: the marginal distributions are independent. Part (c): In steady-state, the queue length at queue 1 at time t is independent of the departure process before time t. Hence, the formula is s 2 /(1 2 ). Part (d): I wanted an 3

expression of the nite-dimensional distributions in terms of the transition (matrix) function P (t). This is just as in (2.8) on page 3 of the CTMC notes, but here the CTMC is twodimensional. The idea is the same. I wanted to see some representation for the transition function too. You can represent the transition function as a solution of a matrix ODE (of innite dimension). Alternatively, P (t) = eQt , but again the state space is two dimensional and innite. It is important to recognize that the two marginal distributions are not independent. The steady-state distribution has product form, but the transient distributions do not.