Empirical Comparison of Uniformization Methods for Continuous-Time Markov Chains

John D. Diener and William H. Sanders
Additional contact information
John D. Diener: The University of Arizona, Department of Electrical and Computer Engineering
William H. Sanders: University of Illinois at Urbana-Champaign, The Center for Reliable and High-Performance Computing Coordinated Science Laboratory

Chapter 29 in Computations with Markov Chains, 1995, pp 547-570 from Springer

Abstract: Abstract Computation of transient state occupancy probabilities of continuous-time Markov chains is important for evaluating many performance, dependability, and performability models. A number of numerical methods have been developed to perform this computation, including ordinary differential equation solution methods and uniformization. The performance of these methods degrades when the highest departure rate in the chain increases with respect to a fixed time point. A new variant of uniformization, called adaptive uniformization (AU), has been proposed that can potentially avoid such degradation, when several state transitions must occur before a state with a high departure rate is reached. However, in general, AU has a higher time complexity than standard uniformization, and it is not clear, without an implementation, when All will be advantageous. This paper presents the results of three different AU implementations, differing in the method by which the “jump probabilities” are calculated. To evaluate the methods, relative to standard uniformization, a C++ class was developed to compute a bound on the round-off error incurred by each implementation, as well as count the number of arithmetic instructions that must be performed, categorized both by operation type and phase of the algorithm they belong to. An extended machine-repairman reliability model is solved to illustrate use of the class and compare the adaptive uniformization implementations with standard uniformization. Results show that for certain models and mission times, adaptive uniformization can realize significant efficiency gains, relative to standard uniformization, while maintaining the stability of standard uniformization.

Keywords: Layered Uniformization; Uniformization Method; Discrete Time Markov Chain; Birth Process; Standard Uniformization (search for similar items in EconPapers)
Date: 1995
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-1-4615-2241-6_29

Ordering information: This item can be ordered from
http://www.springer.com/9781461522416

DOI: 10.1007/978-1-4615-2241-6_29

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().