1) Let N1(t) and N2(t) be independent Poisson processes with rates, λ1 and λ2, respectively. Let N(t) = N1(t) + N2(t).
a) What is the distribution of the time till the next epoch of N2(t)?
b) What is the probability that the next epoch of N(t) is an epoch in N1(t)?
c) What is the distribution of the next epoch of N(t)?
d) What is the mean number of N1(t) epochs before the next epoch of N2(t)?
2) Let {Yn, n ≥ 1} be a sequence of iid random variables with Pr{Yn = 2} = p = 1 - Pr{Yn = -1}.
Let {Xn, n ≥ 0} be de?ned as X0 = 0 and
Xn+1 = (Xn + Yn+1)+ ,
where θ+ = max(θ, 0).
a) Show that {Xn} is a DTMC.
b) An irreducible DTMC with state space, S is positive recurrent if and only if ∃ a function, f(i), ∀i ∈ S, so that E[f(Xn)|Xn = i] < ∞ and E[f(Xn+1) - f(Xn)|Xn = i] < 0.
Use f(i) = i and this result to obtain a suf?cient condition for the DTMC to be positive recurrent.
c) Let Zk be the number of visits to state, 0 in an interval [0.k). Determine, limn→∞ 1/nE(Zn) in terms of the steady state probability vector, π (need not give exact value).
3) For an irreducible DTMC with state space, S, transition probability matrix, P and stationary probability vector, πT , show that if ∃ i ∈ S, πi > 0, then πj > 0, ∀ j ∈ S.
4) Consider a DTMC with state space, S, transition probability matrix, P and stationary probability vector, πT. De?ne ? = diag(πi), i ∈ S. Show that the time-reversal of this process is also a DTMC with transition probability matrix, ?-1 PT?.
Hint: For a time -reversal, process, transition probability, Pij = Pr{Xn-1 = j|Xn = i}. Write this in terms of Baye's rule.
5) Let {Vi, i ≥ 1} and {Wi, i ≥ 1} be independent sequences of iid random variables with distributions, H and G, respectively. Intervals of length, Vi and Wi are placed alternatively on the positive real line from the origin, in the order, (V1,W1, V2,W2, · · ·). Let
Z(t) = 1 t is in a V interval,
0 Otherwise
a) Determine limt→∞ 1/2 0∫ t I{Z(u)=1}du.
b) Determine limt→∞ Pr{Z(t) = 1}.
6) Consider the two queues shown in Fig. 1. Two packets are trapped in this system where the services are exponentially distributed with rates, λ and µ. {X(t)} and {Y (t)} are the queue length processes of the two queues, as shown in Fig. 1.
a) Argue that X(t) is a CTMC and Y (t) is a CTMC. Write their state transition diagrams.
b) Determine limt→∞ P01(t) for X(t).
c) Determine limt→∞ P01(t) for Y (t).
7) Consider a CTMC, X(t), with state space, S = {0, 1, 2, · · · ,N}. Let the CTMC be a birth-death process, i.e., qii+1 = λ, 0 ≤ i ≤ N - 1, qjj-1 = µ, 1 ≤ j ≤ N and qij = 0, j = i, otherwise.
a) Determine, πn, 0 ≤ n ≤ N.
b) (4 points) Let M(t) be the number of transitions from state, n to n + 1, 0 < n < N. Find limt→∞ M(t)t.
Hint: Consider visits to state n and use RRT.
8) There are n machines in a factory. Each machine gets repaired according to a Poisson process of rate, λ, independent of other machines. There are servicemen that ?x the repaired machines. Assume there are n servicemen so that each repaired machine is ?xed by a different service man.
Each service man ?xes a machine according to an exponential distribution, with rate, µ. Let X(t) denote the number of repaired machines in the factory.
a) Show that X(t) is a CTMC.
b) Find the steady state probability, πk = limt→∞ Pr{X(t) = k}.
c) Suppose each working machine produces a revenue, r and each repaired machine costs, c units of repair charges, then determine the average pro?t obtained in a day.
9) Consider an M/G/1 queue with Poisson arrivals at rate, λ. Let the service time distribution be F(x) (density, f(x)), with mean, E(X) = 1
µ and second moment, X2. Let ρ ? = λE(X) = λµ.
a) What is the probability that the server is busy and the server is idle?
b) Show that the mean waiting time, W (mean time in the queue excluding the service time) is W = ρR (1-ρ) , where R is the mean residual service time of the customer in service.
Hint: Use the result of Part # 9a) and write W in terms of residual service time and sum of service times of the others waiting in the queue, using Waldt's Lemma and Little's theorem.
c) Hence, derive the Pollakzek-Kinchine (P-K) mean value formula. Remark: This was the original proof for P-K formula using Little's theorem. This gives the mean value but cannot give the waiting time distribution which the EMC approach discussed in class gives.
d) Assume that whenever the server is idle, it goes into a vacation (like into a sleep or a hibernate mode) with mean vacation time, V and second moment, V 2. Show that the mean waiting time in this case, WV is given by WV = W + (1-ρ)V 2 2V , where W is what you obtained in Part # 9c).
10) Consider the M/G/∞ queue with Poisson arrivals (rate, λ) and in?nite number of servers, each with a generalized service time distribution, F(x) (density, f(x)), with mean service time, E(X) = 1 µ.
Let N(t) be the queue length process at time, t.
a) Show that the probability, p(t) that an arrival in (0, t) is still in service at time, t is p(t) = 1/t R t0 [1 - F(x)]dx.
Hint: Assume that the exact arrival epoch is x. Then write p(t|x), i.e., the probability, p(t) conditioned on x. Then average over, x. What do you know about the distribution of x conditioned on t for a Poisson arrival?
b) Show that Pr{N(t) = n} = e-λtp(t) [λtp(t)]nn!
Hint: First assume that m + n arrivals took place in (0, t). Conditioned on this fact, ?nd the probability that n of them remain at time, t, using the result of Part #10a). Then average over m using the fact that arrivals are Poisson and use the fact that P∞ m=0 αn n! = eα.
c) Hence show that the stationary probability, πn = limt→∞ Pr{N(t) = n} = e-ρ ρnn!,
where ρ
? = λE(X) = λµ.
Remark: We already showed this result for the M/M/∞ queue in class. This shows that the result holds at steady state for an in?nite server system with Poisson arrivals, irrespective of the service time distribution.