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