An Algorithm for Finding Characteristic Roots of Quasi-Triangular Markov Chains
Carl M. Harris, William G. Marchal, Richard W. Tibbs · 1989
Abstract : Numerical root finding problems are quite common in stochastic modeling. However, many solutions stop at the presentation of a probability generating function for the state probabilities. But with increasing easy access to computing power, many problems whose answers were typically left in incomplete form or for which there has been a search for alternative solution methods are currently being reexamined. The class of Markov chains whose transition matrices have quasi-triangular layouts (i.e., those having sub- or super-triangular sets of zeros) is a good case in point. They have an especially nice structure which leads to a rather concise representation for the generating functions. But the complete solution then requires the finding of roots. Fortunately, these problems can be shown to have special properties that make accurate root finding quite feasible, and we thus supply an efficient numerical procedure for solution. Keywords: Applied probability; Computational analysis; Computational probability; Markov chains; Numerical methods; Probability; Queues; Stochastic models. (jhd)