TECHNICAL REPORT BU-CE-0414, BILKENT UNIVERSITY, 
DEPARTMENT OF COMPUTER ENGINEERING

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 to use 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.