In
probability theory
Probability theory or probability calculus is the branch of mathematics concerned with probability. Although there are several different probability interpretations, probability theory treats the concept in a rigorous mathematical manner by expre ...
, a nearly completely decomposable (NCD) Markov chain is a
Markov chain
In probability theory and statistics, a Markov chain or Markov process is a stochastic process describing a sequence of possible events in which the probability of each event depends only on the state attained in the previous event. Informally ...
where the state space can be partitioned in such a way that movement within a partition occurs much more frequently than movement between partitions. Particularly efficient algorithms exist to compute the
stationary distribution Stationary distribution may refer to:
* and , a special distribution for a Markov chain such that if the chain starts with its stationary distribution, the marginal distribution of all states at any time will always be the stationary distribution. ...
of Markov chains with this property.
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
In linear algebra, the main diagonal (sometimes principal diagonal, primary diagonal, leading diagonal, major diagonal, or good diagonal) of a matrix A is the list of entries a_ where i = j. All off-diagonal elements are zero in a diagonal matrix. ...
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
In probability theory and statistics, a Markov chain or Markov process is a stochastic process describing a sequence of possible events in which the probability of each event depends only on the state attained in the previous event. Informally ...
with
transition matrix
::
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.
See also
*
Lumpability In probability theory, lumpability is a method for reducing the size of the state space of some continuous-time Markov chains, first published by Kemeny and Snell.
Definition
Suppose that the complete state-space of a Markov chain is divided into ...
References
{{Reflist
Markov processes