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

作者：Xu Jianhong^*

来源：Applied Mathematics and Computation, 2015, 250: 372-389.

DOI：10.1016/j.amc.2014.11.001

• Mean first passage times
• Markov chains
• Iterative algorithm
• Convergence
• Rank one updates
• Eigenvalues

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.

• 出版日期2015-1-1