An iterative algorithm for computing mean first passage times of Markov chains

摘要

Mean first passage times are an essential ingredient in both the theory and the applications of Markov chains. In the literature, they have been expressed in elegant closed-form formulas. These formulas involve explicit full matrix inversions and, if computed directly, may incur numerical instability.In this paper, we present a new iterative algorithm for computing mean first passage times in a manner that does not rely on explicit full matrix inversions. Results regarding the convergence behavior of this algorithm are also developed.