Page 164 - A First Course In Stochastic Models

MARKOV PROCESSES ON A SEMI-INFINITE STRIP 157

of Theorem 4.2.2 for initial state r. It remains to verify that the result also holds
for any initial state X(0) = i with i = r. This verification proceeds along the same
lines as the proof of the corresponding result in Theorem 3.5.11.
By choosing an appropriate reward structure, Theorem 4.2.2 provides a rigorous
proof of earlier interpretations we gave to the quantities p j and q jk p j .
Corollary 4.3.2 Suppose that the continuous-time Markov chain {X(t)} satisfies
Assumptions 4.1.2 and 4.2.1. Then
(a) For each state k ∈ I, the long-run fraction of time the process is in state k
equals p k with probability 1, independently of the initial state X(0) = i.
(b) For all j, k ∈ I with j = k, the long-run average number of transitions from
state k to state j per unit time equals p k q kj with probability 1, independently of the
initial state X(0) = i.

4.4 MARKOV PROCESSES ON A SEMI-INFINITE STRIP ∗

Many practical (queueing) problems can be modelled as a continuous-time Markov
chain {X(t)} on a semi-infinite strip in the plane. That is, the Markov process has
the two-dimensional state space

I = {(i, s) | i = 0, 1, . . . ; s = 0, 1, . . . , m} (4.4.1)
for some finite positive integer m. Assuming that the continuous-time Markov chain
{X(t)} satisfies Assumption 4.2.1, denote its equilibrium probabilities by p(i, s) for
i = 0, 1, . . . and s = 0, 1, . . . , m. These probabilities are determined by an infinite
system of linear equations. In many cases, however, this infinite system can be
reduced to a finite system of linear equations of moderate size. This can be done
by using the geometric tail approach, discussed for discrete-time Markov chains in
Section 3.4.2. Under rather general conditions the equilibrium probabilities p(i, s)
exhibit a geometric tail behaviour as i → ∞, where the decay factor does not
depend on s. That is, for constants γ s > 0 and a constant η with 0 < η < 1,

p(i, s) ∼ γ s η i as i → ∞, (4.4.2)
where the constant η does not depend on s. Then, for a sufficiently large choice of
integer M, we have for each s that
p(i + 1, s)
≈ η, i ≥ M,
p(i, s)
or equivalently

p(i, s) ≈ η i−M p(M, s), i > M.

∗ This section is more specialized and can be omitted at first reading.