ROUNDING ERRORS IN CERTAIN ALGORITHMS INVOLVING MARKOV-CHAINS

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.