In probability theory, a nearly completely decomposable (NCD) Markov chain is a Markov chain where the state space can be partitioned in such a way that movement within a partition occurs much more frequently than movement between partitions.
[1] Particularly efficient algorithms exist to compute the stationary distribution of Markov chains with this property.
[2] 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.
[3][4] A Markov chain with transition matrix is nearly completely decomposable if ε is small (say 0.1).