状态分类与吸收链：首达、命中与停留时间 | 自在学

03 状态分类与吸收链：把“最终会到哪里”算出来

一条链在几个状态之间反复游走。你想知道的可能不是第 10 步在哪里，而是“从这里出发，最终能不能到达目标？”“到达两个出口中的哪一个，概率分别是多少？”“如果目标一定会到，平均还要等几步？”

我会从下一步可能落在哪里写起。例如一台设备下一步仍在维修，这一步照样消耗时间；如果它进入了报废状态，之后就不可能再恢复运行。把这些去向分清，成功概率和等待时间的方程就有了依据。本章沿着这条思路研究状态分类与吸收链：每次写下一个系数，都能回到图上指出它对应哪条边。

可达、沟通与闭合结构

设 $P$ 是时间齐次的离散时间马尔可夫链的转移矩阵。若存在某个 $n\ge0$ ，使得

p_{ij}^{(n)}>0,

就说从状态 $i$ 可以到达状态 $j$ ，记作 $i\leadsto j$ 。允许 $n=0$ ，所以每个状态都能在零步到达自己。

若 $i\leadsto j$ 且 $j\leadsto i$ ，称 $i,j$ 相互沟通，记作 $i\leftrightarrow j$ 。沟通关系把状态空间分成沟通类。一个沟通类已经包含了所有能彼此往返的状态，不能任意漏掉其中一个。如果从这个类中出发不能以正概率走到类外，就称它是闭沟通类。检查时只需看有没有向外的一步边：若所有一步去向都留在类内，走再多步也出不去。闭类像一间没有出口的房间：链可以在内部移动，却不会跳出去。

两个彼此隔开的闭沟通类，每个类内部可往返

上图蓝色的两个状态可以相互往返，橙色的两个也可以；两个组之间没有边，因此它们都是闭类。现在试着加一条单向边，情况就会变。

考虑状态 $S=\{1,2,3,4\}$ ，其中 $1\leftrightarrow2$ ， $3\leftrightarrow4$ ，并存在边 $2\to3$ ，但没有从回到的路径。于是和是沟通类，是闭类，而不是闭类。分类时看的是“是否存在一条正概率路径”，不是比较某条边的概率大小。

首达时间与首返时间

对目标集合 $A\subseteq S$ ，定义首达时间

\tau_A=\inf\{n\ge0:X_n\in A\}.

也可以把检查的起点推到第 1 步，定义

T_A=\inf\{n\ge1:X_n\in A\},

如果初始状态在目标外，这两个时间相同；区别出现在一开始就在目标内的情形。两种定义都约定空集合的下确界为 $\infty$ ，表示永远没到。当初始状态已经在 $A$ 时， $\tau_A=0$ ； $T_A$ 从第 1 步起检查，不要求先离开 。如果下一步仍在，它就是 1。自环也算一次正时间的返回，不能把它漏掉。

对单个状态 $j$ ， $T_j=\inf\{n\ge1:X_n=j\}$ 在从本身出发时叫首返时间；从其他状态出发，它是到达的首达时间。用从自身出发的首返概率定义：

状态 $i$ 若从 $i$ 出发最终以概率 1 返回 $i$ ，称为常返；否则称为暂态。

周期另外描述允许返回的时间位置，下面用所有正概率返时时刻的最大公因数来定义。它不等于常返性，也不等于平均首返时间。

对有限状态链，图的闭合结构足以判断常返性：闭沟通类内的状态常返，非闭沟通类内的状态暂态。我们来看看“有限”究竟帮了什么忙。

固定闭类中的一个状态 $j$ 。从类里每个状态出发，都能选一条正概率路径到 $j$ ；从 $j$ 自身则选一条正长度的返回路径。状态只有有限个，所以这些路径的长度有一个共同上界 $L$ ，路径概率有一个正的共同下界 $\delta$ 。无论现在落在类中哪里，接下来至多 $L$ 步内碰到 $j$ 的机会至少为。按长度为的时间段反复看，连续段都没碰到的概率至多，它趋于零。闭合保证过程不会跑到没有这种保证的类外，因此最终返回的概率为 1。

相反，从非闭类中的状态 $i$ 可以沿一条不重复经过 $i$ 的路径走出该类；一旦走出，就再也不能回到 $i$ ，否则外部状态也应属于原沟通类。这条路径概率为正，所以有正概率不再返回， $i$ 暂态。把每个沟通类缩成一个点，类与类之间不可能构成有向环；在有限张图上沿出口走，总能找到没有出口的类。再用刚才的有限路径下界，就知道过程以概率 1 最终进入某个闭类。无限状态时未必存在共同的 $L,\delta$ ，不能直接沿用这段证明。

同一条路径从第0步和第1步开始检查，会得到不同的首达与首返时刻

周期的计算不等于等待时间

若状态 $i$ 的可能返时时刻集合为 $\{n\ge1:p_{ii}^{(n)}>0\}$ ，周期是这些时刻的最大公因数。例如只能在偶数步返回，周期至少为 2；若既能 2 步又能 3 步返回，最大公因数为 1，状态非周期。周期描述“时间格点结构”，不告诉我们平均要等多久；平均首返时间还需要进一步计算。

这里取的是所有满足 $p_{ii}^{(n)}>0$ 的 $n\ge1$ 。若一个状态根本没有正时间返回路径，本章不为这个空集合指定周期；不要把它误判成周期 1。比如只有 1→2→1 的两步循环，所有返回长度都是偶数，周期为 2。若还加上 1→3→4→1 的三步循环，就已经有返回长度 2 与 3，最大公因数只能是 1。最短返回仍是两步，却已非周期。

两步和三步返回路径共存，使返时时刻的最大公因数为1

同一沟通类内，有返回路径的状态周期相同。若 $i$ 到 $j$ 有一条 $r$ 步路径， $j$ 回 $i$ 有一条 $s$ 步路径，那么 $r+s$ 是的返回长度；在中间插入任意一条的步返回路径，也是。于是整除两者之差，也就整除。交换两状态再说一次，便得到二者相等。

不要把“能从 i 到 j”理解成“最终一定会从 i 到 j”。可达性只要求存在一条正概率路径；另一条路径可能把链带入一个永远回不来的闭类。首达概率是数值问题，沟通关系是结构问题，两者相关但不相同。

首步分析：首达概率方程从哪里来

令目标集合为 $A$ ，定义

h_i=\mathbb P_i(\tau_A<\infty),

其中 $\mathbb P_i$ 表示初始状态为 $i$ 的概率。若 $i\in A$ ，已经到达目标，所以边界条件是

h_i=1,\qquad i\in A.

若 $i\notin A$ ，按第一步到达的状态 $j$ 分解：

\begin{aligned} h_i &=\sum_{j\in S}\mathbb P_i(X_1=j)\mathbb P_i(\tau_A<\infty\mid X_1=j)\\ &=\sum_{j\in S}p_{ij}h_j. \end{aligned}

第一行是全概率公式；第二行使用马尔可夫性：走到 $j$ 后，之后能否到达目标只由当前状态 $j$ 决定。于是对目标外状态得到线性方程

h_i=\sum_{j\notin A}p_{ij}h_j+\sum_{j\in A}p_{ij}, \qquad i\notin A.

这是写方程时最容易漏掉的地方：目标状态的 $h_j$ 虽然等于 1，但不能把它从求和里消失而忘记贡献；它正是第二项 $\sum_{j\in A}p_{ij}$ 的来源。

方程有解，还要选对那个解

只写 $h_i=\sum_jp_{ij}h_j$ ，不一定能唯一确定答案。例如 0、1 都各自吸收，而目标是。已知，另一个方程却只是，填 0 或 1 都满足代数等式。根据事件，永远停在 0 的路径当然到不了 1，所以真正的。有限状态也可能遇到这种不唯一，关键在边界是否把失败结局说清楚。

一般说来，首达概率是这些边界方程的最小非负解。这个说法可以用短时间问题推出。令

h_i^{[m]}=\mathbb P_i(\tau_A\le m).

第 0 步，目标内为 1，目标外为 0；目标外递推为 $h_i^{[m+1]}=\sum_jp_{ij}h_j^{[m]}$ 。时间越长，已命中的事件只会扩大，故递增到。若是任何满足边界方程的非负解，第 0 步已有；用非负的转移概率逐步相乘，归纳得到。取极限就有。因此不能从一族形式解中随便挑一个“看起来像概率”的向量。

例题一：两条出口的首达概率

状态 $0$ 和 $3$ 都是吸收状态，内部状态为 1、2，转移规则为

P=\begin{pmatrix} 1&0&0&0\\ 0.2&0&0.5&0.3\\ 0&0.4&0&0.6\\ 0&0&0&1 \end{pmatrix}.

求从状态 1 出发最终吸收到状态 3 的概率。设

h_i=\mathbb P_i(\text{最终先到达 3 而不是 0}),

这是一个“目标为 3、另一吸收态为失败边界”的首达问题。

目标和失败边界都明确，首步方程比直接枚举任意长度的路径更稳健；因为内部只有两个状态，解一个二元线性方程组即可。

先写边界：到达 3 后成功，所以

h_3=1

；到达 0 后已经不可能再先到 3，所以

h_0=0

。这两个值不是算出来的，而是由题目中的吸收结构决定的。

状态0与3吸收，状态1和2的全部转移与首步方程

吸收链的矩阵方程

本节的吸收链是有限状态链，至少有一个吸收状态，且每个非吸收状态都能沿正概率路径到达某个吸收状态。仅仅“矩阵中有一个吸收态”还不够：其余地方可能有另一个封闭循环，永远不吸收。

在上述条件下，从每个内部状态各选一条通往吸收态的有限路径，取长度上界 $L$ 与正的概率下界 $\delta$ ，就得到 $\mathbb P_i(\tau_A>kL)\le(1-\delta)^k$ 。这既保证最终吸收，也给出有限的平均吸收时间。对于取非负整数值的等待时间，把“还没停止”的指标从第 0 步起相加，就有，取期望后按每项分组可得

\mathbb E_i\tau_A=\sum_{n\ge0}\mathbb P_i(\tau_A>n)\le L\sum_{k\ge0}(1-\delta)^k=\frac L\delta<\infty.

把非吸收的暂态状态排在前面，吸收状态排在后面，矩阵可以写成规范形

P=\begin{pmatrix}Q&R\\0&I\end{pmatrix}.

其中 $Q$ 描述暂态到暂态的一步转移， $R$ 描述暂态到吸收态的一步转移， $I$ 表示吸收后留在原吸收态。

令 $B$ 为“从每个暂态出发最终吸收到各吸收态”的概率矩阵。首步分析对所有暂态状态同时写出：

B=QB+R.

移项得到

(I-Q)B=R.

在这个有限吸收模型里， $Q^n$ 的第 $i$ 行之和就是第 $n$ 步仍未吸收的概率，它被上述分段几何界控制，因此 $Q^n\to0$ 且各项级数收敛。有限部分和满足 $(I - Q) (I + Q + \dots + Q^{m}$ ；令趋于无穷，就得到

N=(I-Q)^{-1}=I+Q+Q^2+\cdots

存在，称为基本矩阵。于是

B=NR.

注意 $Q$ 的行和可以小于 1，少掉的质量进入了吸收部分，不能把 $Q$ 重新归一化成一个完整转移矩阵。

这个无穷级数也有清楚的概率意义： $(Q^n)_{ij}$ 是从暂态 $i$ 出发，经过 $n$ 步仍在暂态部分并位于 $j$ 的概率；把指标变量 $1_{{n < τ_{A}}$ 从起相加，就是吸收前在的总访问次数。每项的期望为，非负项允许把期望与求和交换，所以总期望是。；这就是级数里不能少掉的原因。矩阵公式既可以用来计算，也帮助解释为什么逆矩阵会出现。

同时重排行列后，转移矩阵分成暂态块Q和出口块R

例题二：用矩阵法同时求两个出口概率

沿用上一题，暂态顺序取 $(1,2)$ ，吸收态顺序取 $(0,3)$ 。则

Q=\begin{pmatrix}0&0.5\\0.4&0\end{pmatrix}, \qquad R=\begin{pmatrix}0.2&0.3\\0&0.6\end{pmatrix}.

上一题只求一个成功概率，递推方程最直观；现在同时求两个吸收出口，矩阵法一次给出整张结果表，也更容易迁移到更多状态。

计算

I-Q=\begin{pmatrix}1&-0.5\\-0.4&1\end{pmatrix}

。其行列式为，因此

期望吸收时间：方程的每个 1 从哪里来

令 $t_i=\mathbb E_i[\tau_A]$ 。这一段仍取 $A$ 为全部吸收状态，沿用刚才的有限吸收条件。目标集合 $A$ 中的状态已经到达，因此

t_i=0,\qquad i\in A.

对 $i\notin A$ ，第一步一定会消耗 1 个时间单位。第一步到 $j$ 后，还需要平均 $t_j$ 步，所以

\begin{aligned} t_i &=1+\sum_{j\in S}p_{ij}t_j\\ &=1+\sum_{j\notin A}p_{ij}t_j. \end{aligned}

第二行使用了边界条件 $t_j=0$ （当 $j\in A$ ）。在暂态子空间中写成列向量：

t=\mathbf 1+Qt, \qquad (I-Q)t=\mathbf1, \qquad t=N\mathbf1.

也可以从每条路径来数：吸收发生在第 $\tau_A$ 步，那么此前的时刻恰好是 $0,1,\ldots,\tau_A-1$ ，总共 $\tau_A$ 个。把各暂态的访问次数加起来再取期望，就得到，与首步方程一致。

这里的常数 1 不能漏掉。若写成 $t=Qt$ ，得到的只能是零解，完全没有反映“至少要走一步”这个事实。若每步耗时不同，也可以把 1 换成每个状态对应的一步成本向量，得到成本到吸收的推广。

例题三：期望吸收时间与概率一起检查

对上面的 $Q$ ，求从状态 1、2 出发的期望吸收时间。

已经算出基本矩阵 $N$ ，直接用 $t=N\mathbf1$ 能同时求两种初始状态，并且可以和首步方程相互检查。

令

\mathbf1=(1,1)^\mathsf T

。由上题的

N

，

t = (\begin{array}{cc} 1.25 & 0.625 \\ 0.5 \end{array}

路径1到2到1到3中，暂态访问次数之和等于三步吸收时间

递推法、矩阵法与模拟：怎样选工具

同一个吸收问题可以有多种表示，但方法选择应由问题结构决定：

只有一个目标、状态图小、需要看清边界来源时，用首步递推。它最适合讲清每个系数为什么出现。
有多个吸收出口，或要同时求所有起点的结果时，用规范形、基本矩阵和线性方程组。矩阵法减少重复书写，也暴露状态排序错误。
状态很多、矩阵稀疏或只需要数值近似时，解线性系统通常比显式计算 $(I-Q)^{-1}$ 更稳定；概念上仍然是在解 $(I-Q)x=b$ ，不必真的求逆矩阵。
模拟适合检查数量级和直觉，不替代方程推导。随机模拟的结果会有误差，尤其是小概率吸收出口需要更多重复次数。

在正文模型里，从 1 出发的成功概率是 $0.75$ ，平均吸收时间是 $1.875$ 。模拟前把这两个数写下来，逐步走一条路径，数一数吸收前在 1、2 各停了几次，再运行一批路径。平均时间应该和两种暂态平均访问次数之和一致，却不必在有限次模拟中恰好等于理论值。修改转移行后，如果内部形成了不通向出口的闭类，实验会指出吸收条件失效；达到模拟步数上限的路径也要单独列出，不能当作已经吸收来计算完整平均时间。

迁移：目标集合、成本与非吸收情形

首步分析并不只用于“到两个吸收出口”。若目标是集合 $A$ ，把所有 $A$ 内状态设成边界即可；若 $A,B$ 不相交，问从状态 $i$ 到 $B$ 前是否先到 $A$ ，就把 $A$ 设为成功边界、设为失败边界。若尚未停止时，在状态记一次非负成本，停止时刻及其后不再记成本，则总成本是。在有限吸收条件下，成本向量有界，期望有限，并满足

v_i=c_i+\sum_jp_{ij}v_j,

在目标上设 $v_i=0$ ，相应内部矩阵方程为 $(I-Q)v=c$ ，所以 $v=Nc$ 。例如正文模型在状态 1、2 每步分别花费 2、5 个单位，从 1 出发的平均总成本为。它也满足、。不要把成本不相同的问题仍写成。首步分析的核心不是“吸收”这个词，而是把第一次动作从剩余问题中分离出来。

非吸收链也可以写首达方程，但要小心：目标可能以小于 1 的概率到达，期望首达时间可能是无穷大；不能因为方程有一个形式解，就自动声称目标必达或期望有限。有限闭类结构和首达概率边界必须先判断。例如正文模型若只把 $\{3\}$ 当作目标，从 1 出发有 $0.25$ 的概率永远停在 0，因而 $\mathbb E_1[\tau_{\{3\}}]=\infty$ ；是到的平均时间，不能换个目标后继续沿用。若允许无穷值，期望首达时间仍是时间首步方程的最小非负解：反复代入所得前项为，任意非负解都不小于它；令增大，正好得到。这里零概率去向的项按零贡献处理，不用做普通实数运算。

先把目标设为 $\{0,3\}$ ，观察两个出口的时间边界都为零。只保留 3 时，预测哪些起点的平均首达时间会变成无穷大，再让实验显示原因。换成 $\{2\}$ ，状态 1 可能在碰到 2 之前就去了出口，命中概率又要重算。最后恢复两个出口、把成本改成 $(2,5)$ ，比较时间方程中的常数 1 与成本方程中的不同常数：矩阵可以复用，右边的量却已经换了。

路径有先后要求时，把必要的历史留下

仍用正文的四状态链，从 1 出发，改问“在吸收到 3 之前，是否已经经过状态 2”。直接走 1→3 虽然成功到达 3，却不符合这次的顺序要求。单独记录当前状态 1 还不够：一直没到过 2 时，和已经走过 1→2→1 时，后续成功事件的条件不同。

加入一个标记，记录“是否访问过 2”。标记为 1 之后不再擦掉，这时最终到 3 的成功概率就是前面算过的 $h_1=0.75,h_2=0.9$ 。从未访问 2 的状态 1 出发，记成功概率为 $g_1$ ；下一步到 0 失败，到 3 也因顺序不符而失败，只有到 2 才进入“已访问”的一层。因此

g_1=0.2\times0+0.5h_2+0.3\times0=0.45.

把当前状态和访问标记合起来，便能用同样的首步方程处理新问题。扩张状态并不意味着一定要把完整历史保存下来；本题只需要一个是或否的记录。如果原图中所有到 3 的路径本来就必须经过 2，额外的顺序条件便没有筛掉任何路径，这时两事件反而相同。练习里会让你检查这种情形。

自测与练习

若 h_i 表示从 i 出发最终到达目标集合 A 的概率，i∈A 时的边界值是什么？

关于吸收链的基本矩阵 N=(I−Q)^{-1}，下列哪些说法正确？

只要状态 i 可以到达目标 j，就一定有从 i 出发最终到达 j 的概率 1。

巩固：写出首步方程

状态 0 是吸收目标，状态 1 每步以 0.3 到 0、以 0.7 留在 1。令 $h_i$ 为最终到达 0 的概率，写出边界和状态 1 的方程，并求 $h_1$ 。

若目标集合为 $A=\{2,3\}$ ，状态 1 一步到 1、2、3 的概率分别为 0.2、0.5、0.3，写出 $h_1=\mathbb P_1(\tau_A<\infty)$ 的首步方程。为什么不能把当作未知量继续求？

变式：分类与周期

某链的状态图中只有边 1→2、2→1、2→3、3→3、4→4，且每条列出的边概率均为正，未列出的边概率为 0。找出沟通类、闭类，并判断状态 1、3、4 的常返/暂态性质。

沟通类是 $\{1,2\}$ 、 $\{3\}$ 、 $\{4\}$ 。因为从 2 可以到 3，却没有从 3 回到 1 或 2， $\{1,2\}$ 不是闭类； $\{3\}$ 和 ${$ 都是闭类。有限闭类中的状态常返，所以 3、4 常返；状态 1 属于会流向闭类而不能返回的暂态类，因此为暂态。状态 1 与 2 是否有自环并不影响这个常返/暂态判断，但会影响周期计算。

一个状态只能在 2、4、6、… 步返回，但也确实存在 2 步和 4 步返回。它的周期是多少？如果又发现存在 3 步返回，周期会怎样改变？

迁移：两种边界与期望时间

一条链的内部状态为 1、2，吸收态为 0、3，且

Q=\begin{pmatrix}0.3&0.4\\0.2&0.5\end{pmatrix}, \qquad R=\begin{pmatrix}0.3&0\\0&0.3\end{pmatrix},

其中吸收态顺序为 $(0,3)$ 。求从状态 1 出发最终在 3 吸收的概率，以及从状态 1 出发的期望吸收时间。要求写明使用的方程或矩阵。

对第 5 题，比较“最终到 3”和“先经过 2，再最终到 3”两事件。从 1 出发时它们相同吗？随后只把 $R$ 的第一行改成 $(0.1,0.2)$ ， $Q$ 与 $R$ 的第二行保持不变，再计算这两个概率。

原模型中状态 1 没有直接到 3 的边，进入 3 的最后一步必从 2 出发，因此两事件相同，概率都是 $4/9$ ，不能仅因为题目多写了“先经过”就断定必须换答案。

修改后新增了从 1 直接到 3 的机会，两事件才分开。普通成功概率满足 $h_1=0.3h_1+0.4h_2+0.2$ 、，解得。对尚未访问 2 的状态 1，直接到 3 不合顺序，所以，得到。差额，正好对应在状态 1 自环若干次后直接跳到 3、始终没去过 2 的路径总概率。

沿用第 5 题的 $Q$ ，但在两个内部状态每步成本分别为 2、5，进入吸收态后不再收费。求从 1 出发的平均总成本，并解释基本矩阵第一行中 $50/27$ 和 $40/27$ 分别表示什么。若忘记计入初始时刻，会少算多少？

由已算的 $N$ ，从 1 出发吸收前在 1、2 的期望访问次数分别为 $50/27,40/27$ 。每次访问按对应成本计费，所以平均总成本为 $2(50/27)+5(40/27)=100/9$ 。这些是包含第 0 步的期望次数，不必是整数。初始状态确定为 1，若漏掉第 0 步就恰好少收 2，而不是少收一个平均成本。

状态 0、2 各自吸收，状态 1 一步到 0、1、2 的概率依次为 $0.2,0.5,0.3$ 。以 2 为唯一目标，写出全部首达概率方程。说明为什么只靠方程有多个非负解，怎样选出实际概率，并判断从 1 出发到 2 的平均首达时间是否有限。

四状态链只有这些正概率边：A→B、B→A、B→C、C→D、D→A。找出从 A 返回的两个循环长度，据此判断整个链的周期。若再添加 D→B，并相应调整 D 行概率以保持和为 1，周期怎样变化？

原来有 A→B→A 的两步循环与 A→B→C→D→A 的四步循环。只列出这两个长度还不够排除别的返回长度；把状态分成 $\{A,C\}$ 与 $\{B,D\}$ ，每步必换组，故所有返回长度都为偶数。有两步返回，周期便是 2。整个状态空间相互沟通，其他状态同周期。添加 D→B 后，B→C→D→B 给出三步循环，而 B→A→B 仍是两步循环，所以周期变成 $\gcd(2,3)=1$ 。

\delta

)

=

I

-

Q^{m + 1}

(I-Q)(I+Q+\cdots+Q^m)=I-Q^{m+1}

,

X_{n}

=

j

}

\mathbf1_{\{n<\tau_A, X_n=j\}}

A

1.25

)

(\begin{array}{c} 1 \\ 1 \end{array})

=

(\begin{array}{c} 1.875 \\ 1.75 \end{array})

.

t=\begin{pmatrix}1.25&0.625\\0.5&1.25\end{pmatrix}\begin{pmatrix}1\\1\end{pmatrix}=\begin{pmatrix}1.875\\1.75\end{pmatrix}.

B

B

4

}

\{4\}

h_{1} = 0.2 h_{0} + 0.5 h_{1} + 0.3

h_1=0.2h_0+0.5h_1+0.3