GTH Algorithm, Censored Markov Chains, and $RG$-Factorization in Block-Form
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866918449709580288 |
|---|---|
| author | Bu, Qihui Zhao, Yiqiang Q. |
| author_facet | Bu, Qihui Zhao, Yiqiang Q. |
| contents | In 1985, Grassmann, Taksar, and Heyman published their celebrated paper, in which they introduced a numerically stable algorithm for computing the stationary probabilities of a finite-state Markov chain, one of the key performance quantities in both theory and applications. This algorithm later became the well-known GTH algorithm (or the state-reduction method) in the literature, becoming one of the standard algorithms in applied probability. Later, this algorithm was extended to deal with the stationary distributions of block-structured Markov chains with repeating rows.
In this paper, we focus on the block-form GTH algorithm and organize it into two parts. In the first part, we connect the block-form GTH algorithm to censored Markov chains and the block-form $RG$-factorization. We show that the forward block-elimination and back block-form substitution of the block-form GTH algorithm are equivalent to solving a system formulated using the $RG$-factorization in two steps. We also show that this connection remains valid when the block-form GTH algorithm is extended to infinite-state Markov chains. It is well known that censoring an infinite-state Markov chain to a finite state space yields a stationary distribution that provides a best approximation to the stationary distribution of the original infinite-state Markov chain.
In the second part, we first derive an explicit expression for the censored Markov chain from the infinite state space to a finite space for Markov chains of $M/G/1$ type. Based on this expression, we propose a renormalized approximated censored transition matrix (RA-CM). The resulting stationary distribution is shown to be asymptotically optimal in terms of approximation error. We compare the approximation error of the RA-CM with the error arising from the last-block-column augmentation. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_14347 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | GTH Algorithm, Censored Markov Chains, and $RG$-Factorization in Block-Form Bu, Qihui Zhao, Yiqiang Q. Numerical Analysis 60-08, 60J22 In 1985, Grassmann, Taksar, and Heyman published their celebrated paper, in which they introduced a numerically stable algorithm for computing the stationary probabilities of a finite-state Markov chain, one of the key performance quantities in both theory and applications. This algorithm later became the well-known GTH algorithm (or the state-reduction method) in the literature, becoming one of the standard algorithms in applied probability. Later, this algorithm was extended to deal with the stationary distributions of block-structured Markov chains with repeating rows. In this paper, we focus on the block-form GTH algorithm and organize it into two parts. In the first part, we connect the block-form GTH algorithm to censored Markov chains and the block-form $RG$-factorization. We show that the forward block-elimination and back block-form substitution of the block-form GTH algorithm are equivalent to solving a system formulated using the $RG$-factorization in two steps. We also show that this connection remains valid when the block-form GTH algorithm is extended to infinite-state Markov chains. It is well known that censoring an infinite-state Markov chain to a finite state space yields a stationary distribution that provides a best approximation to the stationary distribution of the original infinite-state Markov chain. In the second part, we first derive an explicit expression for the censored Markov chain from the infinite state space to a finite space for Markov chains of $M/G/1$ type. Based on this expression, we propose a renormalized approximated censored transition matrix (RA-CM). The resulting stationary distribution is shown to be asymptotically optimal in terms of approximation error. We compare the approximation error of the RA-CM with the error arising from the last-block-column augmentation. |
| title | GTH Algorithm, Censored Markov Chains, and $RG$-Factorization in Block-Form |
| topic | Numerical Analysis 60-08, 60J22 |
| url | https://arxiv.org/abs/2604.14347 |