AN ALGORITHM FOR IDENTIFYING THE ERGODIC SUBCHAINS AND TRANSIENT STATES OF A STOCHASTIC MATRIX,
Abstract
A technique for quickly identifying the significant substructural relationships among states of a Markov chain, which is one of the simplest and most frequently used probability models. In applications, a Markov chain usually represents a physical system whose alternative modes of operation can be limited to a finite number of possibilities called states. The dynamics of such a system are specified by designating the probabilities governing its changes from one state to another over time; these probabilities together comprise the elements of a stochastic matrix, which is the natural vehicle by which Markov chains are represented. An algorithm for identifying the ergodic subchains and transient states of a stochastic matrix is presented. Applications in Markov renewal programming and in the construction of variable length codes are reviewed, and an updating procedure for dealing with certain sequences of stochastic matrices is discussed. The FORTRAN IV computer program for the algorithm is given as an appendix. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Mar 01, 1967
- Accession Number
- AD0649384
Entities
People
- B. L. Fox
- D. M. Landi
Organizations
- RAND Corporation