Discrete-time stochastic processes

The reader should focus on the case e x x 0 on a rst


View Full Document Right Arrow Icon

Unformatted text preview: e of a customer conditional on the service time X of that customer being 1. Find (in terms of C ) the expected system time of a customer conditional on X = 2; (Hint: compare a customer with X = 2 to two customers with X = 1 each); repeat for arbitrary X = x. h) Find the constant C . Hint: use f ) and g); don’t do any tedious calculations. Exercise 6.19. Consider a queueing system with two classes of customers, type A and type B . Type A customers arrive according to a Poisson process of rate ∏A and customers of type B arrive according to an independent Poisson process of rate ∏B . The queue has a FCFS server with exponentially distributed IID service times of rate µ &gt; ∏A + ∏B . Characterize the departure process of class A customers; explain carefully. Hint: Consider the combined arrival process and be judicious about how to select between A and B types of customers. Exercise 6.20. Consider a pre-emptive resume last come ﬁrst serve (LCFS) queueing system with two classes of customers. Type A customer arrivals are Poisson with rate ∏A and Type B customer arrivals are Poisson with rate ∏B . The service time for type A customers is exponential with rate µA and that for type B is exponential with rate µB . Each service time is independent of all other service times and of all arrival epochs. 6.9. EXERCISES 275 Deﬁne the “state” of the system at time t by the string of customer types in the system at t, in order of arrival. Thus state AB means that the system contains two customers, one of type A and the other of type B ; the type B customer arrived later, so is in service. The set of possible states arising from transitions out of AB is as follows: AB A if another type A arrives. AB B if another type B arrives. A if the customer in service (B ) departs. Note that whenever a customer completes service, the next most recently arrived resumes service, so the state changes by eliminating the ﬁnal element in the string. a) Draw a graph for the states of the process, showing all states with 2 or fewer customers and a couple of states with 3 customers (label the empty state as E ). Draw an arrow, labelled by the rate, for each state transition. Explain why these are states in a Markov process. b) Is this process reversible. Explain. Assume positive recurrence. Hint: If there is a transition from one state S to another state S 0 , how is the number of transitions from S to S 0 related to the number from S 0 to S ? c) Characterize the process of type A departures from the system (i.e., are they Poisson?; do they form a renewal process?; at what rate do they depart?; etc.) d) Express the steady state probability Pr {A} of state A in terms of the probability of the empty state Pr {E }. Find the probability Pr {AB } and the probability Pr {AB B A} in terms of Pr {E }. Use the notation ρA = ∏A /µA and ρB = ∏B /µB . e) Let Qn be the probability of n customers in the system, as a function of Q0 = Pr {E }. Show that Qn = (1 − ρ)ρn where ρ = ρA + ρB . Exercise 6.21. a) Generalize Exercise 6.20 to the case in which there are m types of customers, each with independent Poisson arrivals and each with independent exponential service times. Let ∏i and µi be the arrival rate and service rate respectively of the ith user. Let ρi = ∏i /µi and assume that ρ = ρ1 + ρ2 + · · · + ρm &lt; 1. In particular, show, as before that the probability of n customers in the system is Qn = (1 − ρ)ρn for 0 ≤ n &lt; 1. b) View the customers in part a) as Psingle type of customer with Poisson arrivals of rate a P ∏ = i ∏i and with a service density i (∏i /∏)µi exp(−µi x). Show that the expected service time is ρ/∏. Note that you have shown that, if a service distribution can be represented as a weighted sum of exponentials, then the distribution of customers in the system for LCFS service is the same as for the M/M/1 queue with equal mean service time. Exercise 6.22. Consider a k node Jackson type network with the modiﬁcation that each node i has s servers rather than one server. Each server at i has an exponentially distributed service time with rate µi . The exogenous input rate to node i is ρi = ∏0 Q0i and each output from i is switched to j with probability Qij and switched out of the system with probability 276 CHAPTER 6. MARKOV PROCESSES WITH COUNTABLE STATE SPACES Qi0 (as in the text). Let ∏i , 1 ≤ i ≤ k, be the solution, for given ∏0 , to ∏j = k X ∏i Qij ; i=0 1 ≤ j ≤ k and assume that ∏i &lt; sµi ; 1 ≤ i ≤ k. Show that the steady state probability of state m is Pr {m } = k Y pi (mi ), i=1 where pi (mi ) is the probability of state mi in an (M , M , s) queue. Hint: simply extend the argument in the text to the multiple server case. Exercise 6.23. Suppose a Markov process with the set of states A is reversible and has steady state probabilities pi ; i ∈ A. Let B be a subset of A and assume that the process is changed by setting qij = 0 for all i ∈ B , j ∈ B . Assuming that the new process (starting / in B and remining in...
View Full Document

This note was uploaded on 09/27/2010 for the course EE 229 taught by Professor R.srikant during the Spring '09 term at University of Illinois, Urbana Champaign.

Ask a homework question - tutors are online