分解—排序—更新法求解马尔科夫链

论文提出了一种计算有限状态离散时间马尔科夫链平稳分布的算法，算法的核心是块划分马尔科夫链的状态转移图，对分解怕得的状态子空间进行了拓扑排序，然后根据拓扑充列计算每个状态子空间，相应地更新马尔科夫链的实始分布。本算法对求解有限状态离散时间可约马尔科夫链；尤其是当马尔科夫链有非常迟状态且可分成多个块时就非常适用。

Solving Markov Chains Using the Method of Decomposition Sort Regeneration

An algorithm for computing the stationary distribution of finite state discrete time Markov Chains is provided in the paper.The core of the algorithm is partitioning the state transition diagram of a Markov chain,and running a topological sort algorithm to the state sub spaces just divided,and then computing every state sub space and accordingly regenerating the initial distribution of the Markov Chain according to the topological seqence.The algorithm can be used to solve the reducible finite state discrete time Markov Chains,especially to solve the Markov Chain which has trancient states and can be partitioned into many partitions.