Markov Chains are used to model processes such as behavior of queueing networks. Both the short term behavior (e.g., mean first passage times) and the long term behavior (e.g., stationary vector) are of interest, and this work has focused on both of these problems.
The basic computational problem for Markov chains is determining the stationary vector, defining the long-term behavior of the chain. Grassman, Taksar, and Heyman proposed an algorithm that O'Cinneide has shown to compute an approximation to the stationary vector with low relative error in each component. Jason Wu and I developed a block form of the GTH algorithm, more efficient on high performance architectures, and showed that it, too, produces a vector with low relative error. We demonstrated the efficiency of the algorithm on vector processors and on workstations with hierarchical memory [J42]. Iterative methods for finding stationary vectors were studied in [C09].
A great deal of attention has been devoted to computing stationary vectors, but less attention has been given to computational algorithms for other parameters associated with these chains. Daniel Heyman (Bellcore) and I developed and evaluated algorithms for computing the fundamental matrix, the group generalized inverse, and the mean and variance of first passage times for discrete time regular Markov chains [C14] and then studied ill-conditioned problems arising in this area [J44].