×

Numerically stable methods for the computation of exit rates in Markov chains. (English) Zbl 1342.60126

Summary: We consider the exit rate from a finite class of transient states of a continuous-time Markov chain and develop numerically stable methods for the computation with bounded from above approximation error of the steady-state exit rate and the time-dependent exit rate. Finally, we develop an also numerically stable method for the computation with bounded from above approximation error of reachable bounds for the time-dependent exit rate which are independent of the initial probability distribution. Applications for the latter include the cyclic analysis of fault-tolerant systems and the analysis of fault-tolerant systems with unobservable up state. The methods compare well from a computational cost point of view with existing alternatives, some with inferior quality regarding the error control.

MSC:

60J27 Continuous-time Markov processes on discrete state spaces
60J22 Computational methods in Markov chains
60J10 Markov chains (discrete-time Markov processes on discrete state spaces)
65C40 Numerical analysis or methods applied to Markov chains
60J28 Applications of continuous-time Markov processes on discrete state spaces

Software:

CVODE; MPFR; mctoolbox
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Arlat J, Laprie JC (1983) Performance-related dependability evaluation of supercomputer systems. In: Proc. 13rd IEEE annual symp. on fault-tolerant computing. Los Alamitos, IEEE Computer Society Press, pp 276-283
[2] Berman A, Plemmons RJ (1994) Nonnegative Matrices in the Mathematical Sciences. SIAM, Philadelphia · Zbl 0815.15016 · doi:10.1137/1.9781611971262
[3] Byrne GD, Hindmarsh AC (1975) A polyalgorithm for the numerical solution of ordinary differential equations. ACM Trans Math Softw 1:71-96 · Zbl 0311.65049 · doi:10.1145/355626.355636
[4] Carrasco, JA; Pham, H. (ed.), Markovian dependability/performability modeling of fault-tolerant systems, 613-652 (2003), New York · doi:10.1007/1-85233-841-5_34
[5] Carrasco JA (2004) Transient analysis of some rewarded Markov models using randomization with quasistationarity detection. IEEE Trans Comput 53:1106-1120 · doi:10.1109/TC.2004.68
[6] Cohen SD, Hindmarsh AC (1996) CVODE, a stiff/nonstiff ODE solver in C. Comput Phys 10:138-143 · doi:10.1063/1.4822377
[7] Courtois JP (1977) Decomposability: queuing and computer system applications. Academic Press, New York · Zbl 0368.68004
[8] Darroch JN, Seneta E (1965) On Quasi-stationary Distributions in Absorbing Discrete-time Finite Markov Chains. J Appl Probab 2:88-100 · Zbl 0134.34704 · doi:10.2307/3211876
[9] Darroch JN, Seneta E (1967) On Quasi-stationary Distributions in Absorbing Continuous-time Finite Markov Chains. J Appl Probab 4:192-196 · Zbl 0168.16303 · doi:10.2307/3212311
[10] Fousse L, Hanrot G, Lefvre V, Plissier P, Zimmermann P (2007) MPFR: a multiple-precision binary floating-point library with correct rounding. ACM Trans Math Softw 33:1-15 · Zbl 1365.65302 · doi:10.1145/1236463.1236468
[11] Fox BL, Glynn PW (1988) Computing Poisson Probabilities. Commun ACM 31:440-5 · doi:10.1145/42404.42409
[12] Ghasemi A, Yacout S, Ouali MS (2010) Evaluating the reliability function and the mean residual life for equipment with unobservable states. IEEE Trans Reliab 59:45-54 · doi:10.1109/TR.2009.2034947
[13] Gross D, Miller DR (1984) The randomization technique as a modeling tool and solution procedure for transient Markov processes. Oper Res 32:343-361 · Zbl 0536.60078
[14] Higham NJ (2002) Accuracy and Stability of Numerical Algorithms. SIAM, Philadelphia · Zbl 1011.65010 · doi:10.1137/1.9780898718027
[15] (1985) IEEE standard for binary floating-point arithmetic, IEEE Computer Society Press, Los Alamitos · Zbl 0688.60059
[16] Kijima M (1997) Markov processes for stochastic modeling. Chapman & Hall, London · Zbl 0866.60056 · doi:10.1007/978-1-4899-3132-0
[17] Knüsel L (1986) Computation of the Chi-square and Poisson Distribution. SIAM J Sci Stat Comput 7:1022-1036 · Zbl 0617.65150 · doi:10.1137/0907069
[18] Moorsel AP, Sanders WH (1997) Transient solution of Markov models by combining adaptive and standard uniformization. IEEE Trans Reliab 46:430-440 · Zbl 0168.16303
[19] Rubino G, Sericola B (1989) Sojourn times in finite Markov processes. J Appl Probab 27:744-756 · Zbl 0688.60059 · doi:10.2307/3214379
[20] Rubino G (1997) Predicting dependability properties on-line. In: Proc. 16th symp. on reliable distributed systems. IEEE Computer Society Press, Los Alamitos, pp 53-9
[21] Schott JR (1997) Matrix analysis for statistics. Wiley, New York · Zbl 0872.15002
[22] Seneta E (2006) Non-negative matrices and Markov chains. Springer, New York · Zbl 1099.60004
[23] Sismail K (1991) A software tool for fault-tolerant systems in the operational phase. In: Proc. IFAC/IFIP/ENICS/SR.lstems, pp 47-55 · Zbl 0134.34704
[24] Van Der Vorst HA (1992) Bi-CGSTAB: a fast and smoothly converging variant of Bi-CG for the solution of nonsymmetric linear systems. SIAM J Sci Stat Comput 13:631-644 · Zbl 0761.65023 · doi:10.1137/0913035
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.