Rounding errors in certain algorithms involving Markov chains

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Rounding errors in certain algorithms involving Markov chains

Full text

Pdf (723 KB)

Source

ACM Transactions on Mathematical Software (TOMS) archive
Volume 19 , Issue 4 (December 1993) table of contents

Pages: 496 - 508

Year of Publication: 1993

ISSN:0098-3500

Author

Winfried K. Grassmann

Univ. of Saskatchewan

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 6, Downloads (12 Months): 29, Citation Count: 2

Additional Information:

abstract references cited by index terms collaborative colleagues peer to peer

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/168173.168416 What is a DOI?

ABSTRACT

A number of algorithms involving Markov chains contain no subtractions. This property makes the analysis of rounding errors particularly simple. To show this, some principles for analyzing the propagation and generation of rounding errors in algorithms containing no subtraction are discussed first. These principles are then applied in the context of a simple recursive algorithm involving the transient solution of discrete-time Markov chains, Jensen's algorithm, and state reduction. Jensen's algorithm, also known as randomization or uniformization, is an algorithm for finding transient solutions of continuous-time Markov chains. State reduction is a method for finding equilibrium probabilities for discrete-time or continuous-time Markov chains.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Peter B. Andrews, An introduction to mathematical logic and type theory: to truth through proof, Academic Press Professional, Inc., San Diego, CA, 1986
	2	BUNCH, J.F. 1987. The weak and strong stability of algorithms in numerical linear algebra. Linear Algebra Appl. 88-89, 46-66.
	3	DEBOOR, C., AND PINKUS, A. 1977. Backward error analysis for totally positive linear systems. Numer. Math. 27, 4, 485-490.
	4	Bennett L. Fox , Peter W. Glynn, Computing Poisson probabilities, Communications of the ACM, v.31 n.4, p.440-445, April 1988 [doi>10.1145/42404.42409]
	5	GRASSMANN, W.K. 1989. A probabilistic analysis of rounding errors of floating point numbers. Congr. Numeratlum 6g, 171-182_
	6	GRASSMANN, W.K. 1985. The factorization of queueing equations and their interpretation. J. Opl. Res. Soc. 36, 11 (Nov.) 1041 1051.
	7	GRASSMANN, W.K. 1977. Transient solutions in Markovian queueing systems. Comput Oper. Res. 4, 47-53.
	8	GRASSMANN, W. K., AND HEYMAN, D. P. 1993. Computation of steady-state probabilities for infinite-state Markov chains with repeating rows ORSA J. Comput. 5, 3 (Summer).
	9	GRASSMANN, W. K., TAKSAR, M. I., AND HEYMAN, D.P. 1985. Regenerative analysis and steady state dmtributions for Markov chains. Oper. Res. 33, 5 (Sept.-Oct.), 1107-1116.
	10	GRoss, D., AND MmLER, D.R. 1984. The randomization technique as a modelling tool and solution procedure for transient Markov processes. Oper Res. 32, 2 (Mar.-Apr.), 343-361
	11	Daniel P. Heyman, Further comparisons of direct methods for computing stationary distributions of Markov chains, SIAM Journal on Algebraic and Discrete Methods, v.8 n.2, p.226-232, April 1, 1987 [doi>10.1137/0608020]
	12	HEYMAN, D. P., AND REEVES, A. 1989. Numerical solutions arising in Markov chain models ORSA J. Comput 1, t (Winter), 52-60.
	13	Nicholas J. Higham, Bounding the error in Gaussian Elimination for Tridiagonal systems, SIAM Journal on Matrix Analysis and Applications, v.11 n.4, p.521-530, Oct. 1990 [doi>10.1137/0611036]
	14	JENSEN, A. 1953. Markov chains as an aid in the study of Markoff processes. Scand. Actuar. 36, 87-91.
	15	KOHLAS, J. 1986 Numerical computation for mean passage times and absorption probabilities in Markov and semi-Markov models. Z. Oper. Res. 30, A197-A207.
	16	Ulrich W. Kulisch , Willard L. Miranker, Computer Arithmetic in Theory and Practice, Academic Press, Inc., Orlando, FL, 1981
	17	KEMENY, J. G., SNELL, J. L., AND KNAPP, A. W 1966. Denumerable Markov Chains. Van Nostrand, Princeton, N.J.
	18	O'CINNEIDE, 1993. Entrywise perturbation theory and error analysis for Markov chains. Numer. Math. 5, i (May).
	19	STEWART, G. W. 1993. Gaussian elimination, perturbation theory and Markov chains. In Linear Algebra, Markov Chains, and Queuemg Models. C. Meyer and R. J. Ptemmons, Eds. Springer-Verlag, New York, 59 69
	20	STEWART, G. W, AND ZHANG, G. 1990. On a direct method for the solution of nearly uncoupled Markov chains. Numer. Math. 59, 1 (Apr.), 1 11.
	21	James H. Wilkinson, Rounding Errors in Algebraic Processes, Dover Publications, Incorporated, 1994

CITED BY 2

	Juan A. Carrasco, Computation of bounds for transient measures of large rewarded Markov models using regenerative randomization, Computers and Operations Research, v.30 n.7, p.1005-1035, June 2003
	Darryl Wayne Dormuth , Attahiru Sule Alfa, Two finite-difference methods for solving $MAP(t)/PH(t)/1/K$ queueing models, Queueing Systems: Theory and Applications, v.27 n.1-2, p.55-78, 1997