马尔可夫链中稳态概率和吸收概率对比

马尔可夫链中，一旦进入某些状态就会停留在该状态不再出来，这种状态称为吸收态，这种链则称为为吸收链。

一些例子有：

• 金融活动中投资者破产了，无法继续参与投资，破产就可以看作吸收态。
• 对生物体或程序体（比如进程，游戏人物）的生命周期建模，其终结状态就是吸收态。

吸收概率是从某状态出发，最终进入特定吸收态的概率。

稳态概率（平稳分布）是马尔可夫过程持续足够久之后，系统处在各个状态的概率达到稳定时的分布，可以先通过图的结构分析是否会达到稳定，一般条件是图中各个状态都是循环的，即从当前状态出发最终还是会回到该状态，并且状态之间是互相可达的。

计算稳态概率的思维模式是：假设系统已经进入到了稳态，那么随机选一个状态 i 的“先验”概率就是稳态概率 \( \pi_i \)

要计算特定状态 j 的稳态概率 \( \pi_j \) ，意味着 j 的邻居（在稳态时）朝着它走一步之后的全概率还是 \( \pi_j \), 因此有 \( \pi_j = \sum_i p_{ij}\pi_i \), 也可以写成 \( \pi_j = \sum_i \pi_i p_{ij} \)

如果把稳态概率向量化为行向量 \( \vec{\pi} \), 而从 i 到 j 的转移概率写成矩阵 \( P \) 那么这个式子就是 \( \vec{\pi} = \vec{\pi} P \), 是右乘以转移概率矩阵。

把 \( \vec{\pi} \) 看作列向量则写成 \( \vec{\pi} = P^T \vec{\pi} \), 后文以这种形式来讨论。

现在考虑吸收概率，思维也是基于全概率公式，但它不是讨论进入状态 j 这最后一步，而是基于第一步来拆分问题。

假设现在在状态 i, 而某个吸收状态是 j, 那么从 i 出发可能进入其他各状态，然后在其他状态上又以特定的吸收概率进入吸收态，因此有： \( f_j = \sum p_{ij} f_j \)

如果把吸收概率向量化为列向量 \( \vec{f} \), 而从 i 到 j 的转移概率写成矩阵 \( P \) 那么这个式子就是 \( \vec{f} = P\vec{f} \) 。

对比稳态概率方程 \( \vec{\pi} = P^T \vec{\pi} \) 和吸收概率方程 \( \vec{f} = P\vec{f} \)

前者是每个邻居汇聚到一个节点的全概率公式，后者是从一个节点扩散到其他邻居后的全概率公式。

体现到矩阵形式上，区别在于转移概率矩阵是否转置。

但从线性代数视角，都是要求特定矩阵在特征根 1 时的特征向量。

一般的 \( Ax=x \) 方程，可以写成 \( (A-1)x=0 \) ，或者就是 \( Bx=0 \), 如果没有任何问题背景，那么 x=0 是一个平凡的解。 而如果 B 可逆，那么 0 就是唯一解，因为 \( B^{-1}Bx=0 \) 必然成立，没有别的选择。

如果 B 不可逆，x 就会有非 0 解，这种情况意味着有方程组有冗余行，未知变量会比方程更多，因此解会有无穷个。

为了把无穷个约束成唯一解，需要加入问题背景：

如果是稳态概率，我们面对的方程是 \( (P^T-I) \vec{\pi} = 0 \), 根据定义，每个状态都应该有一个非 0 的概率，而概率本身非负的，因此 \( \pi \) 被要求每个元素都大于 0

因此 \( P^T-I \) 必然是不可逆的（为什么可逆的问题后文讨论，目前假设是一切都是顺利的）

但即便如此， \( \vec{\pi} \) 仍然会有无穷个（得到的是解空间）。

因此必须引入额外的条件，由于想计算的是最终系统处于各个状态的概率，这是概率分布，故所有概率之和为 1, 加上这个限制之后解就是唯一的。

切换到吸收概率上，此时面对的方程是 \( (P-I) \vec{f} = 0 \), 每个吸收状态 j 都对应了一个 f，其中第 i 个元素是状态 i 最终被 j 吸收的概率，由于是概率，因此有非负约束，但它们不可能的都是 0, 比如吸收状态 j 本身最终进入自身的概率为 1, 因此 f=0 的平凡解并不可取。

所以 \( P-I \) 必然不可逆。这还体现出，吸收概率不是一个分布，因此没有归一化约束。

f 的约束在于可以指定某些特定状态的概率的具体值，比如吸收状态 j 到自身的吸收概率为 1, 而其他吸收状态到 j 的概率为 0, 通过这种约束，可以把无穷个解变成一个解。

现在问题是 \( P-I \) 和 \( P^T - I \) 为什么是不可逆的，或者说，为什么 P 和 \( P^T \) 都有特征根 1 。

这是因为 P 的第 i 行各个元素表示的是从状态 i 进入状态 j 的转移概率，因此 P 的各行求和均为 1 ：

\[ P \mathbf{1} = \mathbf{1} \] 其中 \(\mathbf{1}\) 是全 1 列向量。这表明 1 是 \(P\) 的一个特征根，\(\mathbf{1}\) 是对应的右特征向量，因此 \(P - I\) 不可逆。

类似的，对于 \(P^T\) 有： \[ \mathbf{1}^T P^T = \mathbf{1}^T \] 即 1 也是 \(P^T\) 的特征根，\(\mathbf{1}^T\) 是左特征向量，因此 \( P^T - I \) 同样不可逆。

当然如果知道 P-I 不可逆，它的转置就是 \( P^T - I \), 而转置不影响可逆性（奇异性），因此可以从 P-I 不可逆直接推导出 \( P^T-I \) 不可逆

额外的问题是，为什么 \( (P^T-I) \vec{\pi} = 0 \) 加上了一个约束解就唯一了？这说明 \( P^T-I \) 不仅不可逆，而且其零空间维度应该是 1 ？

这里回答是，并不一定，比如假设某个马尔科夫链有两个完全独立的子图 A 和 B, 那么如果初始在 A 图中，那么 B 中所有状态稳定概率为 0, 如果初始在 B 中，那么 A 中所有状态稳定概率为 0, 这就有两个稳态概率解。 因此，唯一解只针对那些各个状态都是互相联通的情况。

或者举一个更具体的例子，假设只有三个状态 1,2,3 ，从 1 进入 2 和 3 的转移概率为 1/2 ，而 2 和 3 不转移到其他状态（转移概率为 0），那么 2 和 3 都是吸收态。

如果初始在状态 1 但第一步进入状态 2 或者初始就在状态 2, 那么稳态概率为 (0,1,0) 如果初始在状态 1 但第一步进入状态 3 或者初始就在状态 3, 那么稳态概率为 (0,0,1)

所以不需要求具体求解 \( (P^T-I) \vec{\pi} = 0 \) 也能推测，即便加上归一化约束，\( \vec{\pi} \) 也会有多个解。

实际它有无穷个解：

\[ P = \begin{pmatrix} 0 & \frac12 & \frac12 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix} \]

转置后为： \[ P^T = \begin{pmatrix} 0 & 0 & 0 \\ \frac12 & 1 & 0 \\ \frac12 & 0 & 1 \end{pmatrix} \]

\[ P^T - I = \begin{pmatrix} -1 & 0 & 0 \\ \frac12 & 0 & 0 \\ \frac12 & 0 & 0 \end{pmatrix} \]

第一行可以把其他行都消为 0 ， 因此有 \(\pi_1 = 0\)，\(\pi_2, \pi_3\) 任意实数。

即便加上概率归一化 \(\pi_1+\pi_2+\pi_3=1\) 得 \(\pi_2+\pi_3=1\)，且 \(\pi_2,\pi_3 \ge 0\)。

所以还是有无穷多个解。

不过我们一般会限定范围，即只对那些所有状态之间都能互相到达的链进行稳态分析，这些链对应的转移矩阵 P 中所有元素都是大于 0 的，即每个状态都有一定正概率转移到其他任意状态。

但对于吸收概率，其约束是针对 \( \vec{f} \) 的部分元素的，解是唯一的（这里涉及更复杂一点的证明，不讨论）。

计算稳态概率有一种更自然的思路：先随机选择一个状态（即给定初始分布 \(\vec{v}_0\)，例如某个状态的概率向量），然后跟随马尔可夫链的转移概率不断模拟多步之后的状态分布，写成极限形式为：

\[ \vec{\pi} = \lim_{n \to \infty} (P^T)^n \vec{v}_0 \]

一切顺利情况下，该极限存在且与初始分布无关，即为唯一的平稳分布。

这不同于直接求解静态的 \( \vec{\pi} = P^T \vec{\pi} \) 约束方程。

接着的追问是：为什么转移矩阵 P 会有这种性质，无论初始分布是什么，都会收敛到唯一的分布？

和上节中一样，我们需要一些限制才行，这里要求 P 中所有元素都大于 0 。

为了记号的方便，我们令 \( Q = P^T \) ，接下来分析的是 \( Q^n \) 的性质。

Q 的每一列求和为 1, 写成数学形式为 \( \mathbf{1}^T Q = \mathbf{1}^T \)

那么给定任何概率向量（和为 1 的向量） v, 它满足 \( \mathbf{1}^T \cdot v = 1 \)

Qv 仍然是一个和为 1 的概率向量，因为 \( \mathbf{1}^T \cdot Qv = \mathbf{1}^Tv =1 \)

而 \( Q^2 \) 等于 \( Q [Q_1,Q_2,\dots] \) = \( [Q Q_1,Q Q_2,\dots] \), 这里 Q1 Q2 是 Q 的列，它们是概率向量，所以 \( QQ1, QQ2 \) 等也是概率向量，因此 \( Q^2 \) 还是一个每列求和都为 1 概率矩阵。

这可以推广到对任意 n, \( Q^n \) 都是概率矩阵。

有了这个性质后，再用对角化去理解矩阵的乘方：

假设 Q 能写成 \( S \Lambda S^{-1} \) 形式，那么 \( Q^n = S\Lambda^n S^{-1} \), 其中 \( \Lambda \) 是对角矩阵，对角线上是 Q 的所有特征根。

如果其中最大值小于 1, 那么 n 趋于无穷的时候 \( \Lambda^n \) 趋于 0 矩阵最终为 0 ，这不是我们预期的。

如果其中最大值大于 1, 那么 n 趋于无穷的时候 \( \Lambda^n \) 中大于 1 的项会趋于无穷，这也不符合预期。

如果其中最大值等于 1, 那么 n 趋于无穷的时候 \( \Lambda^n \) 会变成对角线上只有 1 的对角矩阵， \( Q^n \) 在极限下就是某个常数向量，这是我们期望的稳态。

根据上节可知， Q 的每一列求和都是 1, 因此 1 是它的特征根，所以核心问题变成了：为什么特征根为什么最大为 1 ？ 以及为什么 Q 可以对角化？

我们先假设 Q 可以对角化，这样可以证明其特征根最大是 1 ，思路是：

如果 Q 可以对角化，那么 \( Q^n = S\Lambda^n S^{-1} \), 如果最大特征根大于 1, 由于 S 是常数矩阵，那么 \( Q^n \) 会因为 \( \Lambda^n \) 中最大项趋近无穷而导致某些项非常大，因此 \( Q^n \) 不可能是概率矩阵，但前文证明只要 Q 是概率矩阵 \( Q^n \) 也会是概率矩阵。

所以现在问题就剩下一个， Q 为什么可以对角化？

这里的回答是否定的， Q 不一定能对角化，但即便它不能对角化也可以通过谱理论证明其特征值最大为 1 ，本文不作进一步讨论，可搜索 Perron-Frobenius 定理。

吸收链里有一种问题可能比吸收概率更重要，即计算进入某个吸收态 j 的平均期望时间（步数）。

因为吸收态在现实中往往是某个过程的终结，因此分析从开始到结束需要多少步总有现实意义，该问题和吸收概率计算思路非常相似，只是从全概率公式变成了全期望公式。

仍然只关注特定的吸收态 j ，用 \( t_i \) 表示从状态 i 进入到状态 j 的步数期望， \( \vec{t} \) 则是各个状态进入 j 的步长期望。

那么有：

• 若 i 是吸收态，则 \(t_i = 0\)。
• 否则从 i 走出一步，以不同的概率进入其他邻居状态，而从其他状态进入 j 的期望步数仍然被 t 刻画，根据全期望公式有： \(t_i = 1 + \sum_{j} p_{ij} \, t_j\) ；

n 个状态求解 n 个线性方程组，和计算吸收概率一样，只不过这是非齐次的。

在稳定链中，类似的问题是第一次进入某个状态的平均期望步数，全期望公式完全一样，只不过除了要进入的状态 j ，没有其他额外的 \( t_i=0 \) 的状态。

在处理思维模式上，稳态概率计算是先考虑以先验概率 \( \pi_i \) 在状态 i 上，然后以不同条件概率进入到状态 j ，然后用全概率求和各个分支。求解方程组利用的是概率分布的归一化约束得到唯一解。

吸收概率则是先选定某个状态 i, 然后以不同条件概率转移到其他状态并以特定概率被吸收，再用全概率求和各个分支。 求解方程组利用的是自身吸收状态概率为 1, 其他吸收状态上概率为 0 的约束得到唯一解。

它们的区别在于，吸收概率是针对特定吸收状态的，每个吸收态对应一个向量，它不是概率分布。

而稳定概率则是系统在各个状态的概率分布，其求和为 1 。