Mean Passage Times and Nearly Uncoupled Markov Chains

Let P ( 0 ) ∈ Rn × n be a stochastic matrix representing transition probabilities in a Markov Chain. Also, for a matrix A ∈ Rn × n whose row-sums are zero, let P( ε ) ≡ P ( 0 ) + ε A be stochastic and irreducible for all 0 < ε ≤ ε ₘₐₓ, for some εₘₐₓ. Finally, let M( ε ) be a matrix whose $( i, j )$ entry is the mean passage time from state i to state j when transitions are governed by P( ε ). When the Markov chain associated with $P( 0 )$ is decomposable into a number of independent chains plus a set of transient states, some of the entries of M( ε ) have singularities at zero. The orders of these poles define timescales associated with the process when ε is small. An algorithm is developed for computing these orders. The only input required is the supports of $P( 0 )$ and A, making the problem a combinatorial one. Finally, it is shown how the orders of the poles of M( ε ) at zero play a role in developing series expansions for π ( ε ), the stationary distribution of P( ε ).