A stable algorithm for computing the fundamental matrix (I–Q)–1 of a Markov chain is proposed, where Q is a substochastic matrix. The proposed algorithm utilizes the GTH algorithm which is turned out to be stable for finding the steady state distribution of a finite Markov chain. Our algorithm involves no subtractions and therefore loss of significant digits due to cancellation is ruled out completely while Gaussian elimination involves subtractions and thus may lead to loss of accuracy due to cancellation. We present numerical evidence to show that our algorithm achieves higher accuracy than the ordinary Gaussian elimination.
