Abstract
By combining in a novel way the randomization method with the stationary detection technique, we develop two new algorithms for the computation of the expected reward rates of finite, irreducible Markov reward models, with control of the relative error. The first algorithm computes the expected transient reward rate and the second one computes the expected averaged reward rate. The algorithms are numerically stable. Further, it is argued that, from the point of view of run-time computational cost, for medium-sized and large Markov reward models, we can expect the algorithms to be better than the only variant of the randomization method that allows to control the relative error and better than the approach that consists in employing iteratively the currently existing algorithms that use the randomization method with stationarity detection but allow to control the absolute error. The performance of the new algorithms is illustrated by means of examples, showing that the algorithms can be not only faster but also more efficient than the alternatives in terms of run-time computational cost in relation to accuracy.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Abramowitz M, Stegun IA (1964) Handbook of mathematical functions: with formulas, graphs, and mathematical tables. Number 55 in Applied Mathematics Series. Courier Corporation. 10th printing (December 1972), with corrections
Bowerman PN, Nolty RG, Scheuer EM (1990) Calculation of the Poisson cumulative distribution function. IEEE Trans Reliab 39(2):158–161
Carrasco JA (2003a) Solving dependability/performability irreducible Markov models using regenerative randomization. IEEE Trans Reliab 52(3):319–329
Carrasco JA (2003b) Transient analysis of rewarded continuous time Markov models by regenerative randomization with Laplace transform inversion. Comput J 46(1):84–99
Carrasco JA (2004) Transient analysis of some rewarded Markov models using randomization with quasistationarity detection. IEEE Trans Comput 53(9):1106–1120
Carrasco JA (2015) Numerically stable methods for the computation of exit rates in Markov chains. Methodol Comput Appl Probab. To appear
Chen PM, Lee EK, Gibson GA, Katz RH, Patterson DA (1994) RAID: high-performance, reliable secondary storage. ACM Comput Surv 26(2):145–185
Choi KP (1994) On the median of gamma distributions and an equation of Ramanujan. Proc Am Math Soc 121:245–251
Fousse L, Hanrot G, Lefèvre V, Pélissier P, Zimmermann P (2007) MPFR: a multiple-precision binary floating-point library with correct rounding. ACM Trans Math Softw 33(2):13:1–13:15
Fox BL, Glynn PW (1988) Computing Poisson probabilities. Commun ACM 31(4):440–445
Glynn P (1987) Upper bounds on Poisson tail probabilities. Oper Res Lett 6 (1):9–14
Grassmann WK (1977) Transient solutions in Markovian queueing systems. Comput Oper Res 4(1):47–53
Gross D, Miller DR (1984) The randomization technique as a modeling tool and solution procedure for transient Markov processes. Oper Res 32(2):343–361
IEEE754 (1985) IEEE standard for binary floating-point arithmetic. ANSI/IEEE Std 754-1985
IEEE754-2008 (2008) IEEE standard for floating-point arithmetic - redline. IEEE Std 754-2008 (Revision of IEEE Std 754-1985) - Redline
Kijima M (1997) Markov processes for stochastic modeling. Chapman & Hall, London
Knüsel L (1986) Computation of the chi-square and Poisson distribution. SIAM J Sci Stat Comput 7(3):1022–1036
Ogita T, Rump SM, Oishi S (2005) Accurate sum and dot product. SIAM J Sci Comput 26(6):1955–1988
Sericola B (1999) Availability analysis of repairable computer systems and stationarity detection. IEEE Trans Comput 48(11):1166–1172
Sidje RB, Burrage K, MacNamara S (2007) Inexact uniformization method for computing transient distributions of Markov chains. SIAM J Sci Comput 29(6):2562–2580
Stallman RM, et al. (2012) Using the GNU compiler collection. For GCC version 4.7.2. Free Software Foundation
Suñé V, Carrasco JA (2005) Efficient implementations of the randomization method with control of the relative error. Comput Oper Res 32:1089–1114
van Moorsel APA, Sanders WH (1994) Adaptive uniformization. Stoch Model 10(3):619–647
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Suñé, V. Computing the Expected Markov Reward Rates with Stationarity Detection and Relative Error Control. Methodol Comput Appl Probab 19, 445–485 (2017). https://doi.org/10.1007/s11009-016-9490-y
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11009-016-9490-y
Keywords
- Markov reward model
- Markov chain
- Expected reward rate
- Relative error
- Randomization
- Stationarity detection