In
probability theory
Probability theory 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 expressing it through a set o ...
, a nearly completely decomposable (NCD) Markov chain is a
Markov chain
A Markov chain or Markov process is a stochastic model describing a sequence of possible events in which the probability of each event depends only on the state attained in the previous event. Informally, this may be thought of as, "What happe ...
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 of Markov chains with this property.
Definition
Ando and
Fisher
Fisher is an archaic term for a fisherman, revived as gender-neutral.
Fisher, Fishers or The Fisher may also refer to:
Places
Australia
*Division of Fisher, an electoral district in the Australian House of Representatives, in Queensland
*Elect ...
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
A Markov chain or Markov process is a stochastic model describing a sequence of possible events in which the probability of each event depends only on the state attained in the previous event. Informally, this may be thought of as, "What happe ...
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
References
{{Reflist
Markov processes