学术报告：GTH Algorithm, Censored Markov Chains, and RG-Factorization in Block-Form

报告时间：9月12日（星期五）上午 10:30-11:30

报告地点：沙河校区，二教 113

主持人：张美娟 副教授

报告人：赵以强，加拿大卡尔顿大学，教授

报告摘要：In 1985, Grassmann, Taksar and Heyman published their celebrated paper, in which a numerically stable algorithm was introduced for computing the stationary probabilities of a finite-state Markov chain. 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, in 1990, this algorithm was extended to dealing with stationary distributions of block-structured Markov chains with repeating rows by Grassmann and Heyman. In this talk, we first provide probabilistic interpretations of all components of the GTH-algorithm for the block-structured Markov chain. We then show that, in terms of the concept of censoring, the GTH-algorithm can be extended to infinite-state Markov chains. Finally, we demonstrate that the $RG$-factorization is analogous to LU-decomposition in Gaussian elimination, which is equivalent to the GTH-algorithm. It is worthwhile to note that the censored Markov chain produces a minimal error in approximating the stationary distribution for the original chain under the $l_1$-norm.This talk is based on joint research with Qihui Bu.

报告人简介：赵以强博士是加拿大卡尔顿大学理学院终身正教授、卡尔顿-渥太华-魁北克大学统计概率联合研究室主任。历任卡尔顿大学数学统计学院院长、卡尔顿大学理学院副院长（主管科研及研究生工作）、渥太华-卡尔顿数学统计研究院主任、加拿大统计学会概率分会会长、加拿大运筹学会温尼伯分会会长、（国际著名）菲尔兹数学科学研究所董事会成员、英国剑桥大学牛顿学院访问教授等。

赵教授主要从事应用概率和随机运筹邻域的研究，在国际一流权威期刊上发表了150多篇高水平的学术论文，其研究成果被国际同行广泛引用(谷歌引用3000多次)，并得到高度评价，在应用概率，尤其是排队论及相关领域做出了重要的贡献。赵以强教授连续30多年主持多项国家重要科研项目、现担任五种国际主流权威期刊的副主编，包括OR Letters、Queueing Systems、Stochastic Models等。

撰稿人：刘洁

审稿人：邓露