MAST30001 Stochastic Modelling
Tutorial Sheet 9
1. Show that in in M/M/1 queue with arrival rate λ and service rate µ > λ, the
expected lengths of the idle and busy periods are 1/λ and 1/(µ − λ), respectively.
[Hint: the proportion of time the server is idle is equal to the stationary chance the
system is empty.]
Since the arrivals follow a Poisson process (using in particular the memoryless prop-
erty of the exponential), the time between the moment the system clears and the next
arrival is exponential rate λ and so the expected length of an idle period is the ex-
pectation of this exponential, that is, 1/λ.
If b is the expected length of a busy period and π0 = 1−λ/µ is the long run proportion
of time the system is empty, then
π0 =
1/λ
1/λ+ b
,
or b = 1/(µ− λ).
2. A rental car washing facility can wash one car at a time. Cars arrive to be washed
according to a Poisson process with rate 3 per day and the service time to wash a car
is exponential with mean 7/24 days. It costs the company $150 per day to operate
the facility and the company loses $10 per day for each car tied up in the washing
facility. The company can upgrade the facility to get down to a mean service time
of 1/4 days at the cost of $C per day. What’s the largest C can be for this upgrade
to make economic sense?
We can model the number of cars in the wash as an M/M/1 queue with arrival
rate λ = 3 and current service rate µ = 24/7 and so with stationary distribution
geometric−1 with parameter 1− 21/24 = 1/8 having expectation 7. The companies
current cost per day is
150 + 10× 7 = 220.
If the company pays C dollars per day to increase their service rate to 4, then
similarly their new cost per day will be
150 + C + 10× 3 = 180 + C.
Thus they should spend no more than 40 dollars per day to increase their service
rates.
3. (M/G/∞ queue) In a certain communications system, information packets arrive
according to a Poisson process with rate λ per second and each packet is processed in
one second with probability p and in two seconds with probability 1−p, independent
of the arrival times and other service times. Let Nt be the number of packets that
have entered the system up to time t and Xt be the number of packets in the system
(including those being served) at time t.
(a) Is (Xt)t≥0 a Markov chain? (No detailed argument is necessary here, just think
about it heuristically.)
Xt is not a Markov chain because the chance of the chain decreasing by one in
the interval (t, t+ h) given the value of the chain at time t also depends on the
times of the arrivals in the past.
(b) If X0 = 0, what is the distribution of X2?
If At are the arrivals that require one second of service, and Bt are the arrivals
requiring two seconds of service, then At and Bt are independent Poisson pro-
cesses with rates pλ and (1− p)λ. And X2 = (N2 −N1) + B1; the sum of two
independent Poisson variables (using independent increments) with respective
means λ and (1− p)λ. So X2 is Poisson with mean λ(2− p).
(c) IfX0 = 0, is there a “stationary” limiting distribution πk = limt→∞ P (Xt = k)?
If so, what is it?
Xt only depends on the number of arrivals of the two different types in the
interval (t − 2, t) since all arrivals previous to this time have left the system.
As in part (b), we can write Xt = (Nt − Nt−1) + (Bt−1 − Bt−2), and the two
variables in parentheses are independent Poisson with respective means λ and
(1− p)λ. So for t ≥ 2, Xt is Poisson with mean λ(2− p).
(d) If X0 = N0 = 0, what is the joint distribution of Xt and Nt?
When 0 < t ≤ 1, then Xt = Nt and they’re both distributed as Poisson mean
t. The case 1 < t < 2 is similar but easier than t ≥ 2; the latter case we show
here. Assuming t ≥ 2, then as above we write Xt = (Nt−Nt−1)+(Bt−1−Bt−2)
and also Nt = Xt+(At−1−At−2)+Nt−2, and note that by the comments of part
(b), Xt is independent of (At−1−At−2) and these variables are both independent
of Nt−2. So we can write Nt = Xt + Yt, where Yt is a Poisson variable with
mean λ(p+ t− 2), independent of Xt which implies that for 0 ≤ j ≤ n,
P(Xt = j,Nt = n) = P(Xt = j, Yt = n− j)
= P(Xt = j)P(Yt = n− j)
= e−λt
λn
n!
(
n
j
)
(2− p)j(p+ t− 2)n−j.