Reduced System Algorithms for Markov Chains

Ram Lal and U. Narayan Bhat
Additional contact information
Ram Lal: Department of Management Science, California State University, Fullerton, California 92634
U. Narayan Bhat: Department of Statistics, Southern Methodist University, Dallas, Texas 75275

Management Science, 1988, vol. 34, issue 10, 1202-1220

Abstract: A reduced system is a smaller system derived in the process of analyzing a larger system. In solving for steady state probabilities of a Markov chain, generally the solution can be found by first solving a reduced system of equations which is obtained by appropriately partitioning the transition probability (or rate) matrix. Following Lal (Lal, R. 1981. A unified study of algorithms for steady state probabilities in Makov chains. Ph.D. Dissertation, Department of Operations Research and Engineering Management, School of Engineering and Applied Sciences, Southern Methodist University, Dallas, TX 75275.), a Markov chain can be categorized as standard or nonstandard depending on the location of an invertible submatrix necessary for an efficient solution in a transition probability (or rate) matrix. In this paper, algorithms for the determination of steady state probabilities are developed by using (i) a backward recursion which is efficient for standard systems and (ii) a forward recursion which is efficient for nonstandard systems. It is also shown that the backward recursion can be used for finding the first passage time distribution and its mean and variance.

Keywords: reduced system; steady state probabilities; queueing theory (search for similar items in EconPapers)
Date: 1988
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.34.10.1202 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormnsc:v:34:y:1988:i:10:p:1202-1220

Access Statistics for this article

More articles in Management Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().