Page 115 - A First Course In Stochastic Models

COMPUTATION OF THE EQUILIBRIUM PROBABILITIES 107

are determined up to a multiplicative constant by the equilibrium equations

π j = π k p kj , j ∈ I. (3.4.1)
k∈I
The multiplicative constant is determined by the normalizing equation

π j = 1. (3.4.2)
j∈I
In Section 3.4.1 we consider the case of a finite space I and discuss several methods
to compute the equilibrium probabilities π j . The infinite-state model is dealt with
in Section 3.4.2. It is shown that brute-force truncation is not necessary to get a
finite system of linear equations when the state space I = {0, 1, . . . } and the state
probabilities π j exhibit a geometric tail behaviour as j → ∞. For this situation,
which naturally arises in many applications, an elegant computational method for
the state probabilities can be given. Markov chains with a multidimensional state
space are prevalent in stochastic networks and in such applications it often happens
that the equilibrium probabilities are known up to a multiplicative constant. If
the number of states is too large for a direct computation of the multiplicative
constant, the Metropolis–Hastings algorithm and the Gibbs sampler may be used
to obtain the equilibrium probabilities. These powerful methods are discussed in
Section 3.4.3.

3.4.1 Methods for a Finite-State Markov Chain
In general there are two methods to solve the Markov chain equations:

(a) direct methods,

(b) iterative methods.

To discuss these methods, let us assume that the states of the Markov chain are
numbered or renumbered as 1, . . . , N.

Direct methods
A convenient direct method is a Gaussian elimination method such as the
Gauss–Jordan method. This reliable method is recommended as long as the dimen-
sion N of the system of linear equations does not exceed the order of thousands.
3
The computational effort of Gaussian elimination is proportional to N . Reliable
and ready-to-use codes for Gaussian elimination methods are widely available. A
Gaussian elimination method requires that the whole coefficient matrix is stored,
since this matrix must be updated at each step of the algorithm. This explains why
a Gaussian elimination method suffers from computer memory problems when N