Nearly completely decomposable Markov chain explained
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]
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.[3] [4]
Example
A Markov chain with transition matrix
P=\begin{pmatrix}
&
&0&0\\
&
&0&0\\
0&0&
&
\\
0&0&
&
\\
\end{pmatrix}+\epsilon\begin{pmatrix}
-
&0&
&0\\
0&-
&0&
&0&-
&0\\
0&
&0&-
\\
\end{pmatrix}
is nearly completely decomposable if
ε is small (say 0.1).
[5] Stationary distribution algorithms
Special-purpose iterative algorithms have been designed for NCD Markov chains though the multi–level algorithm, a general purpose algorithm,[6] has been shown experimentally to be competitive and in some cases significantly faster.[7]
See also
Notes and References
- Kontovasilis . K. P. . Mitrou . N. M. . Markov-Modulated Traffic with Nearly Complete Decomposability Characteristics and Associated Fluid Queueing Models . Advances in Applied Probability . 27 . 4 . 1144–1185 . 10.2307/1427937 . 1995 . 1427937 . 123810850 .
- Koury . J. R. . McAllister . D. F. . Stewart . W. J. . 10.1137/0605019 . Iterative Methods for Computing Stationary Distributions of Nearly Completely Decomposable Markov Chains . . 5 . 2 . 164–186 . 1984 .
- Ando . A. . Albert Ando. Fisher . F. M. . Franklin M. Fisher. Near-Decomposability, Partition and Aggregation, and the Relevance of Stability Discussions . International Economic Review . 4 . 1 . 53–67 . 10.2307/2525455 . 1963 . 2525455 .
- Courtois . P. J. . Error Analysis in Nearly-Completely Decomposable Stochastic Systems . Econometrica . 43 . 4 . 691–709 . 10.2307/1913078 . 1975 . 1913078 .
- Example 1.1 from Book: 8. Discrete-time Markov chains: two-time-scale methods and applications. limited. George. Yin. Qing. Zhang. Springer. 2005. 978-0-387-21948-6.
- Horton . G. . Leutenegger . S. T. . 10.1145/183019.183040 . A multi-level solution algorithm for steady-state Markov chains . ACM SIGMETRICS Performance Evaluation Review . 22 . 191–200 . 1994 . 10.1.1.44.4560 . 1110664 .
- On the Utility of the Multi-Level Algorithm for the Solution of Nearly Completely Decomposable Markov Chains (ICASE Report No. 94-44). https://web.archive.org/web/20130408131233/http://www.dtic.mil/cgi-bin/GetTRDoc?Location=U2&doc=GetTRDoc.pdf&AD=ADA284423. live. April 8, 2013. Leutenegger . Scott T.. Horton . Graham . June 1994 . We present experimental results indicating that the general- purpose Multi-Level algorithm is competitive, and can be significantly faster than the special-purpose KMS algorithm when Gauss-Seidel and Gaussian Elimination are used for solving the individual blocks. Markov chains, Multi- level, Numerical solution.. NASA. Contractor Report 194929.
