Computing the Fundamental Matrix for a Reducible Markov Chain
Theodore J. Sheskin · 2021
Many important quantities for a reducible Markov chain can be expressed in terms of the fundamental matrix. These quantities include (1) the expected time that the process is in each transient state for each possible transient starting state, (2) the mean time to absorption for each possible transient starting state, and (3) the probabilities of absorption for each possible transient starting state. In this paper a new matrix construction algorithm is presented for computing the fundamental matrix for any finite, reducible Markov chain. The algorithm contains three steps: construction, reduction, and multiplication. The algorithm requires about the same amount of storage and the same number of arithmetic operations as matrix inversion based on the LU decomposition.