Page 165 - A First Course In Stochastic Models

158 CONTINUOUS-TIME MARKOV CHAINS

Usually the constant η can be computed beforehand by solving a non-linear equation
in a single variable. Once η is known, the infinite system of equilibrium equations
is reduced to a finite system of linear equations by replacing any p(i, s) with i > M
by η i−M p(M, s). It turns out that in practical applications a relatively small value
of M usually suffices. As will be seen below, the asymptotic expansion (4.4.2) is
valid in the unloader problem of Example 4.1.2.

Markov processes with quasi-birth-death rates

Suppose that the Markov process {X(t)} satisfies the following assumption.

Assumption 4.4.1 In state (i, s) the only possible transitions are:

• from state (i, s) to state (i + 1, s) with rate λ s (i = 0, 1, . . . ; s = 0, 1, . . . , m),
• from state (i, s) to state (i − 1, s) with rate µ s (i = 1, 2, . . . ; s = 0, 1, . . . , m),

• from state (i, s) to state (i, s + 1) with rate β s (i = 0, 1, . . . ; s = 0, 1, . . . ,
m − 1),
• from state (i, s) to state (i, s − 1) with rate δ s (i = 0, 1, . . . ; s = 1, 2, . . . , m).

It is assumed that the transition rates λ s , µ s , β s and δ s are such that the
Markov chain {X(t)} satisfies Assumption 4.2.1 and thus has a unique equilib-
rium distribution {p(i, s)}. Under Assumption 4.4.1 the equilibrium equations for
the continuous-time Markov chain {X(t)} are as follows. Then for i = 1, 2, . . .
and with 0 ≤ s ≤ m,

(λ s + µ s + β s + δ s )p(i, s) = λ s p(i − 1, s) + µ s p(i + 1, s)
+ β s−1 p(i, s − 1) + δ s+1 p(i, s + 1) (4.4.3)

provided we put β −1 = β m = δ 0 = δ m+1 = 0 and define p(i, −1) = p(i, m+1) =
0. For i = 0 and 0 ≤ s ≤ m,
(λ s + β s + δ s )p(0, s) = µ s p(1, s) + β s−1 p(0, s − 1) + δ s+1 p(0, s + 1). (4.4.4)

Next we use the powerful tool of generating functions. Define for 0 ≤ s ≤ m the
generating function G s (z) by

∞
i,
G s (z) = p(i, s)z |z| ≤ 1.
i=0
For notational convenience, define G −1 (z) = G m+1 (z) = 0. Multiplying both sides
i
of (4.4.3) and (4.4.4) by z and summing over i, we find for each s that