Computing The Discounted Return In Markov And Semi-Markov Chains

This paper addresses the problem of computing the expected discounted return in finite Markov and semi-Markov chains. The objective is to reveal insights into two questions. First, which iterative methods hold the most promise? Second, when are iterative methods preferred to Gaussian elimination? A set of twenty-seven randomly generated problems are used to compare the performance of the methods considered. The observations that apply to the problems generated here are as follows: Gauss-Seidel is not preferred to Pre-Jacobi in general. However, if the matrix is reordered in a certain way and the author’s row sum extrapolation is used, then Gauss Seidel is preferred. Transforming a semi-Markov problem into a Markov one using a transformation that comes from Schweitzer does not yield improved performance. A method that is analogous to what is called SSOR in the numerical analysis literature does yield improved performance, especially when the row sum extrapolation is used only sparingly. This method is then compared to Gaussian elimination and is found to be superior for most of the problems generated.