[2022] CSEE6180 Modeling and Performance Evaluation - Homework5 - Markov Chain
1 A bit of Markov Chain: Let Xn for n ! 1 be a sequence of iid random variables in {0, 1} such that P(Xn = 0) = P(Xn = 1) = 1/2. We are interested in counting the blocks of 3 successful zeros written Nn. When an element appears in a succeeding block, it is not counted anymore (in other words, if I observe {0,0,0,0,1}, I only can use each 0 in a single block so I only have a single block here). We are interested in estimating the limiting distribution f(Nn) of Nn, i.e. limit of Nn/n for n gets toward infinity.
An example: Imagine we observe then (X1,X2,X3,X4,X5,X6,X7,X8) = (1, 0, 0, 0, 0, 0, 0, 1)then Nn = 2 and Nn/n = 2/8 = 1/4.
1. Define a Markov chain Y to model this problem. Clarify its possible states and identify its associated transition matrix Q.
Hint: Consider a Markov Chain counting the number of successive zeros.
2. Is Y irreducible and recurrent positive? If so, compute its stationary distribution.
3. Conclude on the limit of Nn/n.
2 Load Balancing in a barber shop Consider a barber shop with two barbers. Each barber has room for only two customers (including the one getting the haircut). Service time is exponential for both servers with service rate μ. Arrivals to the service station are Poisson with rate !. We consider two policies wherein policy A, customers are routed to either queue with equal probability. Policy B is to do load balancing wherein customers are routed to the shorter queue. Ties are broken randomly. If the selected queue is full, the customer is turned away.
1. For policy A, compute the average throughput and delay (for the accepted customers).
2. For policy B, draw the state transition diagram, then compute the throughput and delay (for the accepted customers).
3 What happens when things break? Consider an M/G/1 queue, where at any time when the server is busy it can fail. The time until the next failure is Exponentially distributed with rate. Once the server fails, it goes into repair mode. The repair time is a generally distributed random variable denoted by R. After the server is repaired, it continues serving the job that it was serving from the point that it left off (i.e., no work is lost). Assume that the repair times are i.i.d. and are independent of the job sizes. Compute the mean response time of a job arriving to this M/G/1 queue.
• Note that Y the total residence time of a job can composed of two parts: (a) the time during which the job receives service, S and (b) the time during which the job is being repaired, TR. Using this fact, compute E[Y ].
• Compute E[Y 2] and conclude on the mean response time of your queue in terms of Y .
Hint: Note that TR and S are not independent. Feel free to use the fact that
E[S · TR] = 2aE[S] · E[TR].
• Bonus: Write your mean response time in terms of S instead and prove that
E[S · TR] = 2aE[S] · E[TR].
4 Stochastic Differential Equations Consider an on-off Markov modulated Poisson process. The rate transition matrix of the continuous time Markov chain describing the on-off process is given by When in state 0, no arrivals are generated, and when in state 1, arrivals are generated with Poisson
rate !.
(a) What is the arrival rate of this process?
(b) Let {N0(t)} and {N1(t)} be two Poisson counters with rate μ0 and μ1 respectively. Let X(t) 2 {0, 1} denote the state of this process. Write a stochastic differential equation to describe dX(t). Use this equation to derive E[X] where X = limt!1 X(t). Finally, use this expression to derive P(X = i), i = 0, 1. Verify your result with ⇡i obtained from Q.
(c) Let M(t) be the process that counts the number of arrivals in [0, t]. Let {N(t)} be a Poisson counter with rate !. Write a stochastic differential equation to describe the behavior of M(t), i.e. dM(t). Use this to derive an expression for limt!1 dM(t)/dt. How do you interpret the result?
