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