Premium
An exact aggregation/disaggregation algorithm for large scale markov chains
Author(s) -
Kim David S.,
Smith Robert L.
Publication year - 1995
Publication title -
naval research logistics (nrl)
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.665
H-Index - 68
eISSN - 1520-6750
pISSN - 0894-069X
DOI - 10.1002/1520-6750(199510)42:7<1115::aid-nav3220420710>3.0.co;2-w
Subject(s) - markov chain , scale (ratio) , computer science , algorithm , mathematical optimization , mathematics , machine learning , physics , quantum mechanics
Abstract 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. In this article 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. © 1995 John Wiley & Sons, Inc.