SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS, VOL.18. NO.2, PP.482-498, 
1997.

TITLE: Quasi Lumpability, Lower-Bounding Coupling Matrices and Nearly 
       Completely Decomposable Markov Chains

AUTHORS: Tugrul Dayar and William J. Stewart

ABSTRACT: In this paper, it is shown that nearly completely decomposable (NCD) 
Markov chains are quasi-lumpable. The state space partition is the natural 
one, and the technique may be used to compute lower and upper bounds on the 
stationary probability of each NCD block. In doing so, a lower-bounding 
nonnegative coupling matrix is employed. The nature of the stationary 
probability bounds is closely related to the structure of this lower-bounding 
matrix. Irreducible lower-bounding matrices give tighter bounds compared with 
bounds obtained using reducible lower-bounding matrices. It is also noticed 
that the quasi-lumped chain of an NCD Markov chain is an ill-conditioned 
matrix and the bounds obtained generally will not be tight. However, under 
some circumstances, it is possible to compute the stationary probabilities of 
some NCD blocks exactly.

KEY WORDS: Markov chains, quasi lumpability, decomposability, stationary
probability, aggregation-disaggregation schemes

AMS SUBJECT CLASSIFICATIONS: 60J10, 60J27, 65U05, 65F05, 65F10, 65F30