The Numerical Treatment of Markov Chains

本项目将研究离散马尔可夫链的数值解，重点是遍历链的稳态向量的计算。虽然这个问题可以归结为一个普通的特征值问题，但它在两个方面是特殊的。首先，所讨论的本征值，即1，是确切知道的。其次，许多应用程序，如排队建模，都有特殊的结构，可以通过计算来利用。因此，提出了各种各样的方法，其中一些方法鲜为人知。这项工作的目标是提高对它们的理论、它们的相互关系和它们的实现，特别是并行实现的理解，从方法的分类开始，然后专注于特别有前途的算法。

This project will investigate the numerical solution of discrete Markov chains, with an emphasis on the computation of the steady-state vector of ergodic chains. Although the problem can be cast as an ordinary eigenvalue problem, it is special in two ways. First, the eigenvalue in question, namely one, is known exactly. Second, many of the applications, such as queuing modeling, have special structure that can be exploited computationally. Consequently, diverse methods have been set forth, some of which are poorly understood. The goal of this work is to improve understanding of their theory, their interrelations, and their implementation, particularly parallel implementations, beginning with a classification of the methods and then focusing on particularly promising algorithms.