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.