QUASI LUMPABILITY, LOWER-BOUNDING COUPLING MATRICES, AND NEARLY COMPLETELY DECOMPOSABLE MARKOV-CHAINS

In this paper, it is shown that nearly completely decomposable (NCD) M arkov chains are quasi-lumpable. The state space partition is the natu ral one, and the technique may be used to compute lower and upper boun ds on the stationary probability of each NCD block. Ig doing so, a low er-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 t ighter bounds compared with bounds obtained Using reducible lower-boun ding matrices. It is also noticed that the quasi-lumped chain of an NC D Markov chain is an ill-conditioned matrix and the bounds obtained ge nerally will not be tight. However, under some circumstances, it is po ssible to compute the stationary probabilities of some NCD blocks exac tly.