Abstract:

In this paper, we provide a review on the GTH algorithm, which it a numerically stable algorithm for computing stationary probabilities of a Markov chain. Mathematically the GTH algorithm is an rearrangement of Gaussian elimination, and therefore they are mathematically equivalent. All components in the GTH algorithm can be interpreted probabilistically based on the censoring concept and each elimination in the GTH algorithm leads to a censored Markov chain. The RG-factorization is a counterpart t。the LU -decomposition for Gaussian elimination. The censored Markov chain can also be treated as an extended version of the GTH algorithm for a system consisting  of  infinitely many linear equations. The censored Markov chain produces a minimal error for approximating  the original chain under the l₁norm.

Key words:

 GTH method, Gaussian elirnination, Markov chains , Censored Markov chains , RG-factorization, Stationary probabilities, Numericai stably algorithms