ROUNDING ERRORS IN CERTAIN ALGORITHMS INVOLVING MARKOV-CHAINS

Authors
Citation
Wk. Grassmann, ROUNDING ERRORS IN CERTAIN ALGORITHMS INVOLVING MARKOV-CHAINS, ACM transactions on mathematical software, 19(4), 1993, pp. 496-508
Citations number
21
Language
INGLESE
art.tipo
Article
Categorie Soggetti
Computer Sciences",Mathematics
ISSN journal
0098-3500
Volume
19
Issue
4
Year of publication
1993
Pages
496 - 508
Database
ISI
SICI code
0098-3500(1993)19:4<496:REICAI>2.0.ZU;2-S
Abstract
A number of algorithms involving Markov chains contain no subtractions . This property makes the analysis of rounding errors particularly sim ple. To show this, some principles for analyzing the propagation and g eneration of rounding errors in algorithms containing no subtraction a re discussed first. These principles are then applied in the context o f a simple recursive algorithm involving the transient solution of dis crete-time Markov chains, Jensen's algorithm, and state reduction. Jen sen's algorithm, also known as randomization or uniformization, is an algorithm for finding transient solutions of continuous-time Markov ch ains. State reduction is a method for finding equilibrium probabilitie s for discrete-time or continuous-time Markov chains.