SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS, VOL.27, NO.2, PP.396-412, 
2005.

TITLE: Computing Moments of First Passage Times to a Subset of States in
       Markov Chains
 
AUTHORS: Tugrul Dayar and Nail Akar

ABSTRACT: This paper presents a relatively efficient and accurate method
to compute the moments of first passage times to a subset of states in 
finite ergodic Markov chains. With the proposed method, the moment 
computation problem is reduced to the solution of a linear system of 
equations with the right-hand side governed by a novel recurrence for 
computing the higher-order moments. We propose using a form of the 
Grassmann-Taksar-Heyman (GTH) algorithm to solve these linear equations. 
Due to the form of the linear systems involved, the proposed method does 
not suffer from the drawbacks associated with GTH in a row-wise sparse 
implementation.

KEY WORDS: Markov chains, unsafe states, first passage times, mean, 
variance, moments, Grassmann-Taksar-Heyman algorithm

AMS SUBJECT CLASSIFICATIONS: 60J10, 60J27, 65F05, 65F10