Page 168 - A First Course In Stochastic Models

MARKOV PROCESSES ON A SEMI-INFINITE STRIP 161

for details. The algorithm in Chapter 3 of Daigle (1991) is in fact a special case
of the spectral expansion method discussed in full generality in Mitrani and Mitra
(1992). This is a general method for computing the equilibrium probabilities of a
Markov process whose state space is a semi-infinite strip in the two-dimensional
plane and whose equilibrium equations can be represented by a vector difference
equation with constant coefficients. The solution of that equation is expressed in
terms of the eigenvalues and eigenvectors of its characteristic polynomial. Another
generally applicable method to compute the equilibrium probabilities for the two-
dimensional Markov process with quasi-birth-death rates is the matrix-geometric
method of Neuts (1981). This method requires solving a matrix quadratic equation.
This can be done by a probabilistic and numerically stable algorithm discussed
in Latouche and Ramaswami (1993). The computational effort of this algorithm
increases logarithmically when the server utilization gets larger. The computational
burden of the spectral method, however, is relatively insensitive to the server uti-
lization of the analysed system. Unlike the Latouche–Ramaswami algorithm, the
spectral method often becomes numerically unreliable when the server utilization
gets very close to 1. For the practitioner, the geometric tail approach is much eas-
ier to apply than the other two methods. This approach combines simplicity with
effectiveness. The two steps of the geometric tail algorithm are:

(a) Compute the zero of a non-linear equation in a single variable.
(b) Solve a finite system of linear equations.

These steps are simple, and standard software can be used to perform them. The
finite system of linear equations is usually relatively small for practical examples.
In general it is not possible to use the above computational methods on two-
dimensional continuous-time Markov chain problems in which both state variables
are unbounded. An example of such a problem is the shortest-queue problem in
which arriving customers are assigned to the shortest one of two separate queues
each having their own server. Special methods for this type of problem are the
so-called compensation method and the power-series algorithm discussed in Adan
et al. (1993), Blanc (1992) and Hooghiemstra et al. (1988).

Example 4.1.2 (continued) Unloading ships with an unreliable unloader

The continuous-time Markov chain in the unloader problem satisfies Assump-
tion 4.4.1 except that the Markov chain cannot take on state (0, 0). The unloader
can only break down when it is in operation. However, the assumption made in the
foregoing analysis can be released somewhat. Assume that for some integer N ≥ 1
the state space I = I 1 ∪ I 2 , where I 1 = {(i, s) | i = N, N + 1, . . . ; s = 0, . . . , m}
and I 2 is a non-empty subset of {(i, s) | i = 0, . . . , N − 1; s = 0, . . . , m}. The
conditions in Assumption 4.4.1 are only assumed for the states (i, s) with i ≥ N.
Further it must be assumed that the only way to enter the set I 1 from the set I 2 is
through the states (N, s). Then a minor modification of the above analysis shows