Nearly completely decomposable Markov chain

Definition

Ando and Fisher define a completely decomposable matrix as one where "an identical rearrangement of rows and columns leaves a set of square submatrices on the principal diagonal and zeros everywhere else." A nearly completely decomposable matrix is one where an identical rearrangement of rows and columns leaves a set of square submatrices on the principal diagonal and small nonzeros everywhere else.

Example

A Markov chain with transition matrix

\begin{pmatrix} \frac{1}{2} & \frac{1}{2} & 0 & 0 \ \frac{1}{2} & \frac{1}{2} & 0 & 0 \ 0 & 0 & \frac{1}{2} & \frac{1}{2} \ 0 & 0 & \frac{1}{2} & \frac{1}{2} \ \end{pmatrix} + \epsilon \begin{pmatrix} -\frac{1}{2} & 0 & \frac{1}{2} & 0 \ 0 & -\frac{1}{2} & 0 & \frac{1}{2} \ \frac{1}{2} & 0 & -\frac{1}{2} & 0 \ 0 & \frac{1}{2} & 0 & -\frac{1}{2} \ \end{pmatrix} is nearly completely decomposable if ε is small (say 0.1).

Stationary distribution algorithms

Special-purpose iterative algorithms have been designed for NCD Markov chains though the multi–level algorithm, a general purpose algorithm, has been shown experimentally to be competitive and in some cases significantly faster.

References

References

1. (1995). "Markov-Modulated Traffic with Nearly Complete Decomposability Characteristics and Associated Fluid Queueing Models". Advances in Applied Probability.
2. (1984). "Iterative Methods for Computing Stationary Distributions of Nearly Completely Decomposable Markov Chains". [[SIAM Journal on Algebraic and Discrete Methods]].
3. (1963). "Near-Decomposability, Partition and Aggregation, and the Relevance of Stability Discussions". International Economic Review.
4. (1975). "Error Analysis in Nearly-Completely Decomposable Stochastic Systems". Econometrica.
5. (2005). "Discrete-time Markov chains: two-time-scale methods and applications". Springer.
6. (1994). "A multi-level solution algorithm for steady-state Markov chains". ACM SIGMETRICS Performance Evaluation Review.
7. (June 1994). "On the Utility of the Multi-Level Algorithm for the Solution of Nearly Completely Decomposable Markov Chains (ICASE Report No. 94-44)".