Page 110 - A First Course In Stochastic Models

102 DISCRETE-TIME MARKOV CHAINS

with probability 1. Using the expressions for the p ij given in Section 3.1, we obtain
for the π j the equilibrium equations

S−1 ℓ S k−1 ℓ

−λ λ −λ λ
π 0 = 1 − e (π 0 + · · · + π s−1 ) + 1 − e π k ,
ℓ! ℓ!
ℓ=0 k=s ℓ=0
s−1 S−j S k−j
−λ λ −λ λ
π j = e π k + e π k , 1 ≤ j ≤ s − 1,
(S − j)! (k − j)!
k=0 k=s
s−1 S−j S k−j
−λ λ −λ λ
π j = e π k + e π k , s ≤ j ≤ S.
(S − j)! (k − j)!
k=0 k=j

S
These equations together with the normalizing equation k=0 π k = 1 determine
uniquely the equilibrium probabilities π j , j = 0, 1, . . . , S. If one of the equilibrium
equations is omitted to obtain a square system of linear equations, the solution of
the resulting system is still uniquely determined.
Example 3.1.3 (continued) The GI/M/1 queue
In this example the Markov chain {X n } describing the number of customers present
just prior to arrival epochs has the infinite state space I = {0, 1, . . . }. In order to
ensure that Assumption 3.3.1 is satisfied, we have to assume that the arrival rate
of customers is less than the service rate. Thus, denoting by λ the reciprocal of the
mean interarrival time, it is assumed that

λ < µ. (3.3.12)
We omit the proof that under this condition Assumption 3.3.1 is satisfied (with
state 0 as regeneration state r). In the GI/M/1 queueing example the equilibrium
probability π j can be interpreted as the long-run fraction of customers who see j
other customers present upon arrival for j = 0, 1, . . . . In particular, 1 − π 0 is the
long-run fraction of customers who have to wait in queue. Using the specification
of the p ij given in Section 3.1, we obtain the equilibrium equations
∞ k+1−j
∞
−µt (µt)
π j = π k e a(t) dt, j ≥ 1. (3.3.13)
0 (k + 1 − j)!
k=j−1
The equilibrium equation for π 0 is omitted since it is not needed. An explicit
solution for the π j can be given. This solution is
j
π j = (1 − η)η , j = 0, 1, . . . (3.3.14)
where η is the unique solution of the equation

∞
η − e −µ(1−η)t a(t) dt = 0 (3.3.15)
0