Page 233 - A First Course In Stochastic Models

226 MARKOV CHAINS AND QUEUES

5.8 Consider an irreducible continuous-time Markov chain with state space I and infinitesi-
mal transition rates q ij . Let {p j , j ∈ I} be the equilibrium distribution of the Markov chain.
Assume that the Markov chain is time reversible and thus has the detailed balance property
(5.1.15). Suppose that the Markov chain is truncated to the subset A ⊂ I. That is, q ij is
changed to 0 for all i ∈ A and j /∈ A. Prove that the equilibrium distribution of the truncated
Markov chain is given by
A p i
i
p = , i ∈ A.
p
k∈A k
This important result is due to Kelly (1979).
5.9 Suppose we wish to determine the capacity of a stockyard at which containers arrive
according to a Poisson process with a rate of λ = 1 per hour. A container finding a full
yard upon arrival is brought elsewhere. The time that a container is stored in the yard is
exponentially distributed with mean 1/µ = 10 hours. Determine the required capacity of
the yard so that no more than 1% of the arriving containers find the yard full. How does the
answer change when the time that a container is stored in the yard is uniformly distributed
between 5 and 15 hours?
5.10 Long-term parkers and short-term parkers arrive at a parking place for cars according
to independent Poisson processes with respective rates λ 1 = 4 and λ 2 = 6 per hour. The
parking place has room for N = 10 cars. Each arriving car which finds all places occupied
goes elsewhere. The parking time of long-term parkers is uniformly distributed between 1
and 2 hours, while the parking time of short-term parkers has a uniform distribution between
20 and 60 minutes. Calculate the probability that a car finds all parking places occupied upon
arrival.
5.11 Consider the loss version of the delay model from Exercise 5.4. In the loss model each
service request finding all c agents occupied upon arrival is lost and has no further influence
on the system. Let p(i 1 , i 2 ) denote the long-run fraction of time that simultaneously i 1
major-language customers are in service and i 2 minor-language customers are in service.
Verify from the equilibrium equations for the state probabilities p(i 1 , i 2 ) that, for some
constant C > 0,
i 1
(λ 1 /µ 1 ) (λ 2 /µ 2 ) i 2
p(i 1 , i 2 ) = C
i 1 ! i 2 !
for all i 1 , i 2 with 0 ≤ i 1 + i 2 ≤ c. Next conclude that the equilibrium distribution of the
number of occupied agents is given by formula (5.2.1) with λ = λ 1 + λ 2 and 1/µ =
(λ 1 /λ) × (1/µ 1 ) + (λ 2 /λ) × (1/µ 2 ).
5.12 Units offered for repair arrive at a repair facility according to a Poisson process with
rate λ. There are c repairmen. Each repairman can handle only one unit at a time. An offered
unit finding all repairmen busy is rejected and handled elsewhere. The repair time of a unit
consists of two phases. The first phase is exponentially distributed with mean 1/µ 1 and the
second one is exponentially distributed with mean 1/µ 2 .
(a) Let p (i 1 , i 2 ) be the equilibrium probability of having i 1 units in repair phase 1 and
i 2 units in repair phase 2. Verify that, for some constant C, the probability p (i 1 , i 2 ) =
i 2
C(λ/µ 1 ) (λ/µ 2 ) /(i 1 !i 2 !) for all i 1 , i 2 .
i 1
(b) What is the equilibrium distribution of the number of busy repairmen?
(c) What is the long-run fraction of offered units that are rejected? Does this loss prob-
ability increase when the two repair phases are more variable than the exponential phases
but have the same means as the exponential phases?
5.13 Consider a continuous-review inventory system in which customers asking for a certain
item arrive according to a Poisson process with rate λ. Each customer asks for one unit of the
item. Customer demands occurring when the system is out of stock are lost. The (S − 1, S)
control rule is used. Under this control rule the base stock is S and a replenishment for