1 实验内容

生成有 100 个状态的齐次马尔科夫链，状态转移矩阵随机生成(在满足完备

性约束下，可以随机由代码设置，注意保证状态有一定比例与其他状态的联通，

比如 3%；也可以自己提前设置好，但要保证有 2 个以上不可约子集)。

1. 将状态空间按常返性和互通性进行分解；
2. 在 1 的基础上对周期不可约马尔可夫链进行分解。

2 理论基础

设 $C$ 为状态空间 I 的非空子集，若对任意 $i\in C\&\&j\notin C$ 都有 $p_{ij}=0$，则称为 $C$ （随机）闭集，若 $C$ 中所有状态是互通的，称 $C$ 是不可约的闭集。若马尔可夫链 { X n } \{X_n\} {Xn​} 的状态空间 $I$ 是不可约的闭集，则称 { X n } \{X_n\} {Xn​} 为不可约的马尔可夫链。

1. 按常返性和互通性进行状态空间的分解

   任一马尔可夫链的状态空间 I，可唯一地分解成有限个或可列个不相交的集 $D,C_1,C_2,...$ 之和，使得:

   1. 每一 $C_n,n=1,2,...$ 是常返态组成的不可约闭集；
   2. $C_n,n=1,2,...$ 中的状态同类，即或全是正常返，或全是零常返，它们有相同的周期，且$f_{jk}=1,j,k\in C_n$ ；
   3. $D$ 是由全体非常返状态组成，自 $C_n$ 中的状态不能到达 $D$ 中的状态。

2. 按对周期不可约马尔可夫链进行分解

   周期为 $d$ 的不可约马氏链，其状态空间 $C$ 可唯一地分解为$ d $​个互不相交的子集之和，即：
   $$C={\cup }_{r=0}^{d-1}{G}_r,G_r\cap G_s=\Phi ,r\ne s$$
   且使自$G_r$中任一状态出发，经一步必转移进入$G_{r+1}$ 中（其中$G_d=G_0$ ）。

3 题目分析

由理论分析中的分解定理可知，对于有限马尔科夫链而言，状态常反与否及按周期的分解均与转移矩阵 $P=(p_{ij})$ 的具体取值无关，而仅仅取决于各 $p_{ij}$ 是否为零。

由此可知，对于有限马尔科夫链的状态分解，我们只需要考虑转移矩阵$P=(p_{ij})$ 相应的邻接矩阵$B=(b_{ij})$ ，其中：
$$B_{ij}=\{\begin{array}{l}0,p_{ij}=0\\ 1,p_{ij}\ne 0\end{array}i,j=0,1,2,...,n-1$$
当且仅当 $b_{ij}=1$ 时，表示状态 $i$ 可一步到达状态 $j$。

我们可以看到，若状态 $i$ 可到达状态 $j$，则存在长度至多为 $n-1$ 的路径从 $i$ 到达 $j$。因而为求各节点的闭包，只需要计算 $B$ 的可达矩阵 $\overline{B}$​：
$$\overline{B}=B+B^2+\cdots +B^n$$
其中乘法、加法均为布尔运算， $\overline{B}$ 的第$i,j$项 $\overline{b_{ij}}=1$ 表示自 $i$ 出发必可在有限步到达 $j$； $\overline{b_{ij}}=0$ 表示永远不可能达到 $j$。

通过以上分析可知，相对于直接计算 $n$ 步转移矩阵来判断可达，转化为可达矩阵的布尔运算大大减少了计算量。可以将其转为一个有向图算法。

4 按常返性和互通性对状态空间进行分解算法流程

4.1 强连通性和强连通分量

有向图中的强连通性是一种顶点之间等价关系，它有着以下性质:

• 自反性：任意顶点 v 和自己都是强连通的。
• 对称性：如果 v 和 w 是强连通的，那么 w 和 v 也是强连通的。
• 传递性：如果 v 和 w 是强连通的且 w 和 x 也是强连通的，那么 v 和 x 也是强连通的。

作为一种等价关系，强连通性将所有顶点分为了一些等价类，每个等价类都是由相互均为强连通的顶点的最大子集组成的。我们将这些子集称为强连通分量，请见图 1。样图含有 5 个强连通分量。

图 1 强连通分量示意图

4.2 基于有向图 Kosaraju 算法的有限马尔科夫链状态分解

1. 读入转移矩阵，生成有向图 $G$（若$p_{ij}\ne 0$，则有一条从 $i$ 指向 $j$ 的边）。
2. 利用 Kosaraju 算法得到有向图 $G$ 中所有的强连通分量。
3. 遍历每个强连通分量，若一个强连通分量中的节点不能达到另一个强连通分量，说明此强连通分量是一个不可约的闭集 $C$；若可以达到另一个强连通分量，则说明此分量中的节点是非常反的，属于子集 $D$
4. 验证算法正确性。

4.3 算法正确性证明

1. 所有的强连通分量满足分量中的节点相互连通（对于马尔科夫链而言，就是状态可达），并且不会和其他强连通分量中的节点相互连通。现用反证法证明如下：若强连通分量 $C_1$ 中的节点 $i$ 与另一强连通分量 $C_2$ 中的节点 $j$ 相互可达，是强连通的，那么对于 $C_1$ 中的其他节点 $k$ 均可通过 $i$ 到达 $j$ ，$j$ 也可以通过 $i$ 到达 $k$ ，那么明 $j,k$ 是强连通的，按照有向图强连通分量的定义，$j$ 也将属于 $C_1$ ，而本身 $j$ 不属于 $C_1$ ，所以说明，若 $C_1$ 一个最大不可约的。
2. 若强连通分量中的节点不能到达另一个强连通分量，那么此分量是一个闭集，通过 4.2 算法的第三步可以找出所有的闭集，剩余的强连通分量必然是由非常反的状态（节点），用反证法证明：若剩余的强连通分量（即可从本强连通分量到另一个强连通分量）中的节点（状态）$i$是常反的，那么从$i$能通过$i$所在的强连通分量到达其余强连通分量$j$，然后再回到$i$，那么说明$i\to j\to i$，那也可$i\to j\to i\to j$，那么说明$i$, 在同一强连通分量中，然而 Kosaraju算法保证$i,j$不在同一强连通分量中，与假设矛盾，所以剩余的强连通分量中的节点都是非常反的，属于集合𝐷。
3. 在算法第三步中不可达到外部的强连通分量是否是周期相同的？由上两步分析可知，不可达到外部的强连通分量是一个不可约闭集，因为强连通分量的状态是相互连通的，周期必然相等。

由以上两个证明，可以得知，通过这种方法能成功对有限马尔科夫链进行状态分解。

4.4 算法复杂度分析

假设有限图节点（状态）数量为𝑉，有向边数量为𝐸，算法复杂度分析分为两个部分：

1. Kosaraju 算法的复杂度为$O(V+E)$。
2. 4.2 算法流程的第三步，也是遍历一次所有的边和节点，所以复杂度也是$O(V+E)$。

综上，整个算法的复杂度为 $O(V+E)$。

5 按周期对不可约闭集进行分解

1. 选取不可约闭集$C_i$的某一状态$p$，记其为集合$G1$；
2. 由邻接矩阵得到 $G1$ 中每一状态的所有下一步可达状态，将其全体记为集合$G2$，将$G2$ 输出保存得到$C_i$周期性分解的子集之一$G_j$ ；
3. 将第二步所得$G2$ 记为当前的$G1$，循环第二步操作直至所有状态都归于某一$G_j,j=1,2,\cdots ,r$。

由上述步骤，可将某不可约闭集$C_i$​分按周期分解为互不相交子集之并：
$$C_i=\sum _{j=1}^r{G}_i$$

6 对例题分解验证算法正确性

例：设不可约马氏链的状态空间为 $C=1,2,3,4,5,6$，转移矩阵为

状态转移有向图为：

为了能有按常返性和互通性进行状态空间的分解的功能，我加上了第七个状态，此状态能达到 2,3,4 状态。算法输出结果如下图：

然后按周期对不可约马尔科夫链进行状态分解，结果如下：

由实验结果可知，本次设计满足要求。

7 代码使用

只需在 main 函数中修改常量 N 和 ratio 的值即可修改代码，原始的代码是例题的解决，作为一个测试，测试代码的正确性。如需使用随机生成的数据，请将下图的中的第一行注释，第二三行取消注释。

8 总结

具体代码大家可以下载，需要积分，因为我觉得通过上面的分析，自己写也是可行的，希望参考这篇文章的同学们先自己实现。
【有限马尔科夫链状态分解+Kosaraju 算法】代码下载