Kim, David S.; Smith, Robert L. An exact aggregation/disaggregation algorithm for large scale Markov chains. (English) Zbl 0834.60100 Nav. Res. Logist. 42, No. 7, 1115-1128 (1995). Summary: Many Markov chain models have very large state spaces, making the computation of stationary probabilities very difficult. Often the structure and numerical properties of the Markov chain allows for more efficient computation through state aggregation and disaggregation. We develop an efficient exact single pass aggregation/disaggregation algorithm which exploits structural properties of large finite irreducible mandatory set decomposable Markov chains. The required property of being of mandatory set decomposable structure is a generalization of several other Markov chain structures for which exact aggregation/disaggregation algorithms exist. Cited in 2 Documents MSC: 60K30 Applications of queueing theory (congestion, allocation, storage, traffic, etc.) 60J20 Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.) Keywords:computation of stationary probabilities; aggregation/disaggregation algorithm; decomposable structure PDFBibTeX XMLCite \textit{D. S. Kim} and \textit{R. L. Smith}, Nav. Res. Logist. 42, No. 7, 1115--1128 (1995; Zbl 0834.60100) Full Text: DOI References: [1] Cao, Journal of the Association for Computing Machinery 32 pp 702– (1985) · Zbl 0628.65145 · doi:10.1145/3828.214137 [2] Introduction to Stochastic Processes, Prentice Hall, New Jersey, 1975. · Zbl 0341.60019 [3] Structural Decomposition of Markovian Systems, Stanford University, Ph.D. Thesis, 1986. [4] Feinberg, Operations Research 35 pp 282– (1987) [5] Guardabassi, Operations Research 18 pp 324– (1970) [6] Haviv, SIAM J. Numerical Analysis 24 pp 952– (1987) [7] and , Finite Markov Chains, D. Van Nostrand, Princeton, N.J., 1960. [8] Aggregation in Large Scale Markov Chains, University of Michigan, Ann Arbor, Ph.D. Thesis, 1990. [9] and , ”An Exact Aggregation Algorithm for a Special Class of Markov Chains,” Department of Industrial and Operations Engineering, University of Michigan, Ann Arbor, Technical Report 89–2 (1989). [10] Meyer, SIAM Review 31 pp 240– (1989) [11] ”Aggregation Methods for Large Markov Chains,” In Mathematical Computer Performance and Reliability, and (Eds.), Elsevier Science Publishers B.V. North Holland, Amsterdam, 1984. [12] ”A Survey of Aggregation-Disaggregation in Large Markov Chains.” in (Ed.), Numerical Solution of Markov Chains, Marcel Dekker, New York, 1990. [13] Sumita, Journal of the Operations Research Society of Japan 33 pp 279– (1988) [14] Sumita, Commun. Statist-Stochastic Models 5 pp 63– (1989) This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.