Stiffness-tolerant methods for transient analysis of stiff Markov chains

Three methods for numerical transient analysis of Markov chains, the modified Jensen's method (Jensen's method with steady-state detection of the underlying DTMC and computation of Poisson probabilities using the method of Fox and Glynn [1]), a third-order L-stable implicit Runge-Kutta method, and a second-order L-stable method, TR-BDF2, are compared. These methods are evaluated on the basis of their performance (accuracy of the solution and computational cost) on stiff Markov chains. Steady-state detection in Jensen's method results in large savings of computation time for Markov chains when mission time extends beyond the steady-state point. For stiff models, computation of Poisson probabilities using traditional methods runs into underflow problems. Fox and Glynn's method for computing Poisson probabilities avoids underflow problems for all practical problems and yields highly accurate solutions. We conclude that for mildly stiff Markov chains, the modified Jensen's method is the method of choice. For stiff Markov chains, we recommend the use of the L-stable ODE methods. If low accuracy (upto eight decimal places) is acceptable, then TR-BDF2 method should be used. If higher accuracy is desired, then we recommend third-order implicit Runge-Kutta method. © 1994.

Duke Scholars

Author Kishor S. Trivedi Electrical and Computer Engineering