×

An exact aggregation/disaggregation algorithm for large scale Markov chains. (English) Zbl 0834.60100

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.

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.)
PDFBibTeX XMLCite
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.