Misplaced Pages

Nearly completely decomposable Markov chain

Article snapshot taken from Wikipedia with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.

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. Particularly efficient algorithms exist to compute 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 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 with transition matrix

P = ( 1 2 1 2 0 0 1 2 1 2 0 0 0 0 1 2 1 2 0 0 1 2 1 2 ) + ϵ ( − 1 2 0 1 2 0 0 − 1 2 0 1 2 1 2 0 − 1 2 0 0 1 2 0 − 1 2 ) {\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}}}

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

References

  1. 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. JSTOR 1427937. S2CID 123810850.
  2. ^ 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.
  3. 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. JSTOR 2525455.
  4. Courtois, P. J. (1975). "Error Analysis in Nearly-Completely Decomposable Stochastic Systems". Econometrica. 43 (4): 691–709. doi:10.2307/1913078. JSTOR 1913078.
  5. 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.
  6. Horton, G.; Leutenegger, S. T. (1994). "A multi-level solution algorithm for steady-state Markov chains". ACM SIGMETRICS Performance Evaluation Review. 22: 191–200. CiteSeerX 10.1.1.44.4560. doi:10.1145/183019.183040. S2CID 1110664.
  7. Leutenegger, Scott T.; Horton, Graham (June 1994). On the Utility of the Multi-Level Algorithm for the Solution of Nearly Completely Decomposable Markov Chains (ICASE Report No. 94-44) (PDF) (Technical report). NASA. Contractor Report 194929. Archived from the original on April 8, 2013. 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.
Category: