Page 122 - A First Course In Stochastic Models

114 DISCRETE-TIME MARKOV CHAINS

This equation can be shown to have s roots in the interior of the unit circle |w| ≤
1. Assume now that the roots w 1 , . . . , w s are distinct (as is typically the case
in applications). Then, by a standard result from the theory of linear difference
equations, there are constants c 1 , . . . , c s such that

s
j

π j = c k w j ≥ r. (3.4.10)
k
k=1
The root w k having the largest modulus must be real and positive. Why? Denoting
this root by η, the asymptotic expansion (3.4.5) then follows.

Example 3.1.3 (continued) The GI /M/1 queue

The Markov chain {X n } describing the number of customers present just prior to
arrival epochs satisfies Condition B with
r = 0 and s = 1,

as directly follows from the one-step transition probabilities p ij given in (3.1.2).
The constants α k are given by

1−k
∞ (µt)
−µt
α k = e a(t) dt, k ≤ 1.
0 (1 − k)!
It is directly verified that α 1 > 0 and
1 kα k = 1 − µ/λ < 0. Thus we can
k=−∞
directly conclude from (3.4.10) that the equilibrium probabilities π j are of the form
j
γ η for all j ≥ 0 for constants γ > 0 and 0 < η < 1. The characteristic equation
(3.4.9) coincides with the equation (3.3.15).
Next we give an application in which Condition A is used to establish the
asymptotic expansion (3.4.5).

Example 3.4.1 A discrete-time queueing model

Messages arrive at a communication system according to a Poisson process with
rate λ. The messages are temporarily stored in a buffer which is assumed to have
infinite capacity. There are c transmission channels. At fixed clock times t =
0, 1, . . . messages are taken out of the buffer and are synchronously transmitted.
Each channel can only transmit one message at a time. The transmission time of
a message is one time slot. Transmission of messages can only start at the clock
times t = 0, 1, . . . . It is assumed that

λ < c,

that is, the arrival rate of messages is less than the transmission capacity.