Linear Least Square Method for the Computation of the Mean First Passage Times of Ergodic Markov Chains
Yaming Chen *
Nanjing University Press, Nanjing, P.R. China.
*Author to whom correspondence should be addressed.
Abstract
An efficient and accurate iterative scheme for the computation of the mean first passage times ( MFPTs) of ergodic Markov chains has been presented. Firstly, the computation problem of MFPTs is transformed into a set of linear equations. It has been proven that each of these equations is compatible and their minimal norm solutions constitute MFPTs. A new presentation of the MFPTs is also derived. Using linear least square algorithms, some numerical examples compared with the finite algorithm of Hunter [6] and iterative algorithm of J. Xu [7] are given. These results show that the new algorithm is suitable for large sparse systems.
Keywords: Markov chain, Stochastic matrix, Mean rst passage times, Moore-Penrose inverse, Linear least square