Page 120 - A First Course In Stochastic Models

112 DISCRETE-TIME MARKOV CHAINS

π j
lim = η.
j→∞ π j−1
In other words, for a sufficiently large integer M,

π j ≈ π M η j−M , j ≥ M.

Replacing π j by π M η j−M for j ≥ M in equations (3.4.1) and (3.4.2) leads to the
following finite set of linear equations:

M

π j = a jk π k , j = 0, 1, . . . , M − 1,
k=0
M−1
π M

π j + = 1,
1 − η
j=0
where for any j = 0, 1, . . . , M − 1 the coefficients a jk are given by
p kj , k = 0, 1, . . . , M − 1,

a jk =
∞ i−M
i=M η p ij , k = M.
How large an M should be chosen has to be determined experimentally and
depends, of course, on the required accuracy in the calculated values of the equilib-
rium probabilities. However, empirical investigations show that in specific appli-
cations remarkably small values of M are already good enough for practical pur-
poses. We found in all practical examples that the system of linear equations is
non-singular, irrespective of the value chosen for M. An appropriate value of M is
often in the range 1–200 when a reasonable accuracy (perhaps seven-digit accu-
racy) is required for the equilibrium probabilities. A Gaussian elimination method
is a convenient method for solving linear equations of this size. Fast and reliable
codes for Gaussian elimination are widely available. The geometric tail approach
combines effectivity with simplicity.

Conditions for the geometric tail behaviour
A useful but technical condition for (3.4.5) to hold can be given in terms of
j
∞
the generating function
j=0 j z of the equilibrium probabilities π j . In many
π
applications the following condition is satisfied.

∞ j
Condition A (a) The generating function j=0 j z for |z| ≤ 1 has the form
π
∞
N(z)
j
π j z = , (3.4.6)
D(z)
j=0