Nearly completely decomposable Markov chain
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
- [math]\displaystyle{ P = \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} }[/math]
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[2] 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
References
- ↑ Kontovasilis, K. P.; Mitrou, N. M. (1995). "Markov-Modulated Traffic with Nearly Complete Decomposability Characteristics and Associated Fluid Queueing Models". Advances in Applied Probability 27 (4): 1144–1185. doi:10.2307/1427937.
- ↑ 2.0 2.1 Koury, J. R.; McAllister, D. F.; Stewart, W. J. (1984). "Iterative Methods for Computing Stationary Distributions of Nearly Completely Decomposable Markov Chains". SIAM Journal on Algebraic and Discrete Methods 5 (2): 164–186. doi:10.1137/0605019.
- ↑ Ando, A.; Fisher, F. M. (1963). "Near-Decomposability, Partition and Aggregation, and the Relevance of Stability Discussions". International Economic Review 4 (1): 53–67. doi:10.2307/2525455.
- ↑ Courtois, P. J. (1975). "Error Analysis in Nearly-Completely Decomposable Stochastic Systems". Econometrica 43 (4): 691–709. doi:10.2307/1913078.
- ↑ Example 1.1 from Yin, George; Zhang, Qing (2005). Discrete-time Markov chains: two-time-scale methods and applications. Springer. p. 8. ISBN 978-0-387-21948-6. https://archive.org/details/discretetimemark00ying_757.
- ↑ Horton, G.; Leutenegger, S. T. (1994). "A multi-level solution algorithm for steady-state Markov chains". ACM SIGMETRICS Performance Evaluation Review 22: 191–200. doi:10.1145/183019.183040.
- ↑ Template:Cite tech report
 |  |
