03 状态分类与吸收链：把“最终会到哪里”算出来 一条链在几个状态之间反复游走。你想知道的可能不是第 10 步在哪里，而是“从这里出发，最终能不能到达目标？”“到达两个出口中的哪一个，概率分别是多少？”“如果目标一定会到，平均还要等几步？”
我会从下一步可能落在哪里写起。例如一台设备下一步仍在维修，这一步照样消耗时间；如果它进入了报废状态，之后就不可能再恢复运行。把这些去向分清，成功概率和等待时间的方程就有了依据。本章沿着这条思路研究状态分类与吸收链：每次写下一个系数，都能回到图上指出它对应哪条边。
可达、沟通与闭合结构 设 P P P n ≥ 0 n\ge0 n ≥ 0
p i j ( n ) > 0 , p_{ij}^{(n)}>0, p ij ( n ) > 0 , 就说从状态 i i i j j j i ⇝ j i\leadsto j i ⇝ j n = 0 n=0 n = 0
若 i ⇝ j i\leadsto j i ⇝ j j ⇝ i j\leadsto i j ⇝ i i , j i,j i , j i ↔ j i\leftrightarrow j i ↔ j
上图蓝色的两个状态可以相互往返，橙色的两个也可以；两个组之间没有边，因此它们都是闭类。现在试着加一条单向边，情况就会变。
考虑状态 S = { 1 , 2 , 3 , 4 } S=\{1,2,3,4\} S = { 1 , 2 , 3 , 4 } 1 ↔ 2 1\leftrightarrow2 1 ↔ 2 3 ↔ 4 3\leftrightarrow4 3 ↔ 4 2 → 3 2\to3 2 → 3 3 , 4 3,4 3 , 4 1 , 2 1,2 1 , 2 { 1 , 2 } \{1,2\} { 1 , 2 } { 3 , 4 } \{3,4\} { 3 , 4 } { 3 , 4 } \{3,4\} { 3 , 4 } { 1 , 2 } \{1,2\} { 1 , 2 }
首达时间与首返时间 对目标集合 A ⊆ S A\subseteq S A ⊆ S
τ A = inf { n ≥ 0 : X n ∈ A } . \tau_A=\inf\{n\ge0:X_n\in A\}. τ A = inf { n ≥ 0 : X n ∈ A } . 也可以把检查的起点推到第 1 步，定义
T A = inf { n ≥ 1 : X n ∈ A } , T_A=\inf\{n\ge1:X_n\in A\}, T A = inf { n ≥ 1 : X n ∈ A } , 如果初始状态在目标外，这两个时间相同；区别出现在一开始就在目标内的情形。两种定义都约定空集合的下确界为 ∞ \infty ∞ A A A τ A = 0 \tau_A=0 τ A = 0 T A T_A T A 不要求先离开 A A A 。如果下一步仍在 A A A
对单个状态 j j j T j = inf { n ≥ 1 : X n = j } T_j=\inf\{n\ge1:X_n=j\} T j = inf { n ≥ 1 : X n = j } j j j j j j
状态 i i i i i i i i i
周期另外描述允许返回的时间位置，下面用所有正概率返时时刻的最大公因数来定义。它不等于常返性，也不等于平均首返时间。
对有限状态链，图的闭合结构足以判断常返性：闭沟通类内的状态常返，非闭沟通类内的状态暂态。我们来看看“有限”究竟帮了什么忙。
固定闭类中的一个状态 j j j j j j j j j L L L δ \delta δ L L L j j j δ \delta δ L L L k k k ( 1 − δ ) k (1-\delta)^k ( 1 − δ ) k
相反，从非闭类中的状态 i i i i i i i i i i i i L , δ L,\delta L , δ
周期的计算不等于等待时间 若状态 i i i { n ≥ 1 : p i i ( n ) > 0 } \{n\ge1:p_{ii}^{(n)}>0\} { n ≥ 1 : p ii ( n ) > 0 }
这里取的是所有满足 p i i ( n ) > 0 p_{ii}^{(n)}>0 p ii ( n ) > 0 n ≥ 1 n\ge1 n ≥ 1
同一沟通类内，有返回路径的状态周期相同。若 i i i j j j r r r j j j i i i s s s r + s r+s r + s i i i j j j n n n r + n + s r+n+s r + n + s d ( i ) d(i) d ( i ) n n n d ( j ) d(j) d ( j )
不要把“能从 i 到 j”理解成“最终一定会从 i 到 j”。可达性只要求存在一条正概率路径；另一条路径可能把链带入一个永远回不来的闭类。首达概率是数值问题，沟通关系是结构问题，两者相关但不相同。
首步分析：首达概率方程从哪里来 令目标集合为 A A A
h i = P i ( τ A < ∞ ) , h_i=\mathbb P_i(\tau_A<\infty), h i = P i ( τ A < ∞ ) , 其中 P i \mathbb P_i P i i i i i ∈ A i\in A i ∈ A
h i = 1 , i ∈ A . h_i=1,\qquad i\in A. h i = 1 , i ∈ A . 若 i ∉ A i\notin A i ∈ / A j j j
h i = ∑ j ∈ S P i ( X 1 = j ) P i ( τ A < ∞ ∣ X 1 = j ) = ∑ j ∈ S p i j h 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} h i = j ∈ S ∑ P i ( X 1 = j ) P i ( τ A < ∞ ∣ X 1 = j ) = j ∈ S ∑ p ij h j . 第一行是全概率公式；第二行使用马尔可夫性：走到 j j j j j j
h i = ∑ j ∉ A p i j h j + ∑ j ∈ A p i j , i ∉ A . h_i=\sum_{j\notin A}p_{ij}h_j+\sum_{j\in A}p_{ij},
\qquad i\notin A. h i = j ∈ / A ∑ p ij h j + j ∈ A ∑ p ij , i ∈ / A . 这是写方程时最容易漏掉的地方：目标状态的 h j h_j h j ∑ j ∈ A p i j \sum_{j\in A}p_{ij} ∑ j ∈ A p ij
方程有解，还要选对那个解 只写 h i = ∑ j p i j h j h_i=\sum_jp_{ij}h_j h i = ∑ j p ij h j { 1 } \{1\} { 1 } h 1 = 1 h_1=1 h 1 = 1 h 0 = h 0 h_0=h_0 h 0 = h 0 h 0 = 0 h_0=0 h 0 = 0
一般说来，首达概率是这些边界方程的最小非负解 。这个说法可以用短时间问题推出。令
h i [ m ] = P i ( τ A ≤ m ) . h_i^{[m]}=\mathbb P_i(\tau_A\le m). h i [ m ] = P i ( τ A ≤ m ) . 第 0 步，目标内为 1，目标外为 0；目标外递推为 h i [ m + 1 ] = ∑ j p i j h j [ m ] h_i^{[m+1]}=\sum_jp_{ij}h_j^{[m]} h i [ m + 1 ] = ∑ j p ij h j [ m ] h i [ m ] h_i^{[m]} h i [ m ] h i h_i h i x x x x ≥ h [ 0 ] x\ge h^{[0]} x ≥ h [ 0 ] x ≥ h [ m ] x\ge h^{[m]} x ≥ h [ m ] x ≥ h x\ge h x ≥ h
例题一：两条出口的首达概率 状态 0 0 0 3 3 3
P = ( 1 0 0 0 0.2 0 0.5 0.3 0 0.4 0 0.6 0 0 0 1 ) . 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}. P = 1 0.2 0 0 0 0 0.4 0 0 0.5 0 0 0 0.3 0.6 1 . 求从状态 1 出发最终吸收到状态 3 的概率。设
h i = P i ( 最终先到达 3 而不是 0 ) , h_i=\mathbb P_i(\text{最终先到达 3 而不是 0}), h i = P i ( 最终先到达 3 而不是 0 ) , 这是一个“目标为 3、另一吸收态为失败边界”的首达问题。
目标和失败边界都明确，首步方程比直接枚举任意长度的路径更稳健；因为内部只有两个状态，解一个二元线性方程组即可。
先写边界：到达 3 后成功，所以
h 3 = 1 h_3=1 h 3 = 1 ；到达 0 后已经不可能再先到 3，所以
h 0 = 0 h_0=0 h 0 = 0 。这两个值不是算出来的，而是由题目中的吸收结构决定的。
从状态 1 首步可能到 0、2、3，因此
h 1 = 0.2 h 0 + 0.5 h 2 + 0.3 h 3 = 0.5 h 2 + 0.3 h_1=0.2h_0+0.5h_2+0.3h_3=0.5h_2+0.3 h 1 = 0.2 h 0 + 0.5 h 2 + 0.3 h 3 = 0.5 h 2 + 0.3 。从状态 2 首步可能到 1、3，因此
h 2 = 0.4 h 1 + 0.6 h 3 = 0.4 h 1 + 0.6 h_2=0.4h_1+0.6h_3=0.4h_1+0.6 h 2 = 0.4 h 1 + 0.6 h 3 = 0.4 h 1 + 0.6 。每一项都是“首步概率 × 首步后成功概率”。
代入第二式：
h 1 = 0.5 ( 0.4 h 1 + 0.6 ) + 0.3 = 0.2 h 1 + 0.6 h_1=0.5(0.4h_1+0.6)+0.3=0.2h_1+0.6 h 1 = 0.5 ( 0.4 h 1 + 0.6 ) + 0.3 = 0.2 h 1 + 0.6 。所以
0.8 h 1 = 0.6 0.8h_1=0.6 0.8 h 1 = 0.6 ，得到
h 1 = 0.75 h_1=0.75 h 1 = 0.75 ，再得
h 2 = 0.4 × 0.75 + 0.6 = 0.9 h_2=0.4\times0.75+0.6=0.9 h 2 = 0.4 × 0.75 + 0.6 = 0.9 。
检查范围：
0 ≤ h 1 , h 2 ≤ 1 0\le h_1,h_2\le1 0 ≤ h 1 , h 2 ≤ 1 ，而
h 2 = 0.4 h 1 + 0.6 h_2=0.4h_1+0.6 h 2 = 0.4 h 1 + 0.6 表示从 2 出发要么直接成功，要么回 1 后继续；代入结果确实比
h 1 h_1 h 1 大。结论是从状态 1 出发最终在 3 吸收的概率为 0.75，在 0 吸收的概率为 0.25；两者和为 1，也验证了没有遗漏吸收结局。
吸收链的矩阵方程 本节的吸收链是有限状态链，至少有一个吸收状态，且每个非吸收状态都能沿正概率路径到达某个吸收状态。仅仅“矩阵中有一个吸收态”还不够：其余地方可能有另一个封闭循环，永远不吸收。
在上述条件下，从每个内部状态各选一条通往吸收态的有限路径，取长度上界 L L L δ \delta δ P i ( τ A > k L ) ≤ ( 1 − δ ) k \mathbb P_i(\tau_A>kL)\le(1-\delta)^k P i ( τ A > k L ) ≤ ( 1 − δ ) k τ A = ∑ n ≥ 0 1 { τ A > n } \tau_A=\sum_{n\ge0}\mathbf1_{\{\tau_A>n\}} τ A = ∑ n ≥ 0 1 { τ A > n } L L L
E i τ A = ∑ n ≥ 0 P i ( τ A > n ) ≤ L ∑ k ≥ 0 ( 1 − δ ) k = L δ < ∞ . \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. E i τ A = n ≥ 0 ∑ P i ( τ A > n ) ≤ L k ≥ 0 ∑ ( 1 − δ ) k = δ L < ∞. 把非吸收的暂态状态排在前面，吸收状态排在后面，矩阵可以写成规范形
P = ( Q R 0 I ) . P=\begin{pmatrix}Q&R\\0&I\end{pmatrix}. P = ( Q 0 R I ) . 其中 Q Q Q R R R I I I
令 B B B
B = Q B + R . B=QB+R. B = QB + R . 移项得到
( I − Q ) B = R . (I-Q)B=R. ( I − Q ) B = R . 在这个有限吸收模型里，Q n Q^n Q n i i i n n n Q n → 0 Q^n\to0 Q n → 0 ( I − Q ) ( I + Q + ⋯ + Q m ) = I − Q m + 1 (I-Q)(I+Q+\cdots+Q^m)=I-Q^{m+1} ( I − Q ) ( I + Q + ⋯ + Q m ) = I − Q m + 1 m m m
N = ( I − Q ) − 1 = I + Q + Q 2 + ⋯ N=(I-Q)^{-1}=I+Q+Q^2+\cdots N = ( I − Q ) − 1 = I + Q + Q 2 + ⋯ 存在，称为基本矩阵。于是
B = N R . B=NR. B = N R . 注意 Q Q Q Q Q Q
这个无穷级数也有清楚的概率意义：( Q n ) i j (Q^n)_{ij} ( Q n ) ij i i i n n n j j j 1 { n < τ A , X n = j } \mathbf1_{\{n<\tau_A, X_n=j\}} 1 { n < τ A , X n = j } n = 0 n=0 n = 0 j j j ( Q n ) i j (Q^n)_{ij} ( Q n ) ij N i j N_{ij} N ij 初始时刻也计一次，吸收时刻不计入暂态访问 ；这就是级数里不能少掉 I I I
例题二：用矩阵法同时求两个出口概率 沿用上一题，暂态顺序取 ( 1 , 2 ) (1,2) ( 1 , 2 ) ( 0 , 3 ) (0,3) ( 0 , 3 )
Q = ( 0 0.5 0.4 0 ) , R = ( 0.2 0.3 0 0.6 ) . Q=\begin{pmatrix}0&0.5\\0.4&0\end{pmatrix},
\qquad
R=\begin{pmatrix}0.2&0.3\\0&0.6\end{pmatrix}. Q = ( 0 0.4 0.5 0 ) , R = ( 0.2 0 0.3 0.6 ) . 上一题只求一个成功概率，递推方程最直观；现在同时求两个吸收出口，矩阵法一次给出整张结果表，也更容易迁移到更多状态。
计算
I − Q = ( 1 − 0.5 − 0.4 1 ) I-Q=\begin{pmatrix}1&-0.5\\-0.4&1\end{pmatrix} I − Q = ( 1 − 0.4 − 0.5 1 ) 。其行列式为
1 − 0.2 = 0.8 1-0.2=0.8 1 − 0.2 = 0.8 ，因此
N = ( I − Q ) − 1 = 1 0.8 ( 1 0.5 0.4 1 ) = ( 1.25 0.625 0.5 1.25 ) . N=(I-Q)^{-1}=\frac1{0.8}\begin{pmatrix}1&0.5\\0.4&1\end{pmatrix}=\begin{pmatrix}1.25&0.625\\0.5&1.25\end{pmatrix}.
N = ( I − Q ) − 1 = 0.8 1 ( 1 0.4 0.5 1 ) = ( 1.25 0.5 0.625 1.25 ) . 相乘得到
B = N R = ( 1.25 0.625 0.5 1.25 ) ( 0.2 0.3 0 0.6 ) = ( 0.25 0.75 0.1 0.9 ) . B=NR=\begin{pmatrix}1.25&0.625\\0.5&1.25\end{pmatrix} \begin{pmatrix}0.2&0.3\\0&0.6\end{pmatrix} =\begin{pmatrix}0.25&0.75\\0.1&0.9\end{pmatrix}. B = N R = ( 1.25 0.5 0.625 1.25 ) ( 0.2 0 0.3 0.6 ) = ( 0.25 0.1 0.75 0.9 ) . 第一行对应从状态 1 出发，分别在 0、3 吸收的概率；第二行对应从状态 2 出发。
检查每行和为 1：
0.25 + 0.75 = 1 0.25+0.75=1 0.25 + 0.75 = 1 ，
0.1 + 0.9 = 1 0.1+0.9=1 0.1 + 0.9 = 1 。同时与首步递推的
h 1 = 0.75 , h 2 = 0.9 h_1=0.75,h_2=0.9 h 1 = 0.75 , h 2 = 0.9 一致。矩阵的列顺序是
( 0 , 3 ) (0,3) ( 0 , 3 ) ，如果交换吸收态顺序，结果列也必须同步交换。
期望吸收时间：方程的每个 1 从哪里来 令 t i = E i [ τ A ] t_i=\mathbb E_i[\tau_A] t i = E i [ τ A ] A A A A A A
t i = 0 , i ∈ A . t_i=0,\qquad i\in A. t i = 0 , i ∈ A . 对 i ∉ A i\notin A i ∈ / A j j j t j t_j t j
t i = 1 + ∑ j ∈ S p i j t j = 1 + ∑ j ∉ A p i 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 i = 1 + j ∈ S ∑ p ij t j = 1 + j ∈ / A ∑ p ij t j . 第二行使用了边界条件 t j = 0 t_j=0 t j = 0 j ∈ A j\in A j ∈ A
t = 1 + Q t , ( I − Q ) t = 1 , t = N 1. t=\mathbf 1+Qt,
\qquad (I-Q)t=\mathbf1,
\qquad t=N\mathbf1. t = 1 + Qt , ( I − Q ) t = 1 , t = N 1 . 也可以从每条路径来数：吸收发生在第 τ A \tau_A τ A 0 , 1 , … , τ A − 1 0,1,\ldots,\tau_A-1 0 , 1 , … , τ A − 1 τ A \tau_A τ A t i = ∑ j N i j t_i=\sum_jN_{ij} t i = ∑ j N ij
这里的常数 1 不能漏掉。若写成 t = Q t t=Qt t = Qt
例题三：期望吸收时间与概率一起检查 对上面的 Q Q Q
已经算出基本矩阵 N N N t = N 1 t=N\mathbf1 t = N 1
令
1 = ( 1 , 1 ) T \mathbf1=(1,1)^\mathsf T 1 = ( 1 , 1 ) T 。由上题的
N N N ，
t = ( 1.25 0.625 0.5 1.25 ) ( 1 1 ) = ( 1.875 1.75 ) . 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}.
t = ( 1.25 0.5 0.625 1.25 ) ( 1 1 ) = ( 1.875 1.75 ) . 手工写方程可检查第一行：
t 1 = 1 + 0.5 t 2 = 1 + 0.875 = 1.875 t_1=1+0.5t_2=1+0.875=1.875 t 1 = 1 + 0.5 t 2 = 1 + 0.875 = 1.875 ；第二行：
t 2 = 1 + 0.4 t 1 = 1 + 0.75 = 1.75 t_2=1+0.4t_1=1+0.75=1.75 t 2 = 1 + 0.4 t 1 = 1 + 0.75 = 1.75 。两种方法一致。
解释结果：从状态 1 出发平均 1.875 步吸收，从状态 2 出发平均 1.75 步吸收。虽然状态 2 到成功出口的概率更高，但“吸收到任意出口”的时间取决于它在暂态之间来回的结构；平均时间不是成功概率的简单函数。
递推法、矩阵法与模拟：怎样选工具 同一个吸收问题可以有多种表示，但方法选择应由问题结构决定：
只有一个目标、状态图小、需要看清边界来源时，用首步递推。它最适合讲清每个系数为什么出现。
有多个吸收出口，或要同时求所有起点的结果时，用规范形、基本矩阵和线性方程组。矩阵法减少重复书写，也暴露状态排序错误。
状态很多、矩阵稀疏或只需要数值近似时，解线性系统通常比显式计算 ( I − Q ) − 1 (I-Q)^{-1} ( I − Q ) − 1 ( I − Q ) x = b (I-Q)x=b ( I − Q ) x = b
模拟适合检查数量级和直觉，不替代方程推导。随机模拟的结果会有误差，尤其是小概率吸收出口需要更多重复次数。
在正文模型里，从 1 出发的成功概率是 0.75 0.75 0.75 1.875 1.875 1.875
迁移：目标集合、成本与非吸收情形 首步分析并不只用于“到两个吸收出口”。若目标是集合 A A A A A A A , B A,B A , B i i i B B B A A A A A A B B B i i i c i c_i c i ∑ n = 0 τ A − 1 c X n \sum_{n=0}^{\tau_A-1}c_{X_n} ∑ n = 0 τ A − 1 c X n
v i = c i + ∑ j p i j v j , v_i=c_i+\sum_jp_{ij}v_j, v i = c i + j ∑ p ij v j , 在目标上设 v i = 0 v_i=0 v i = 0 ( I − Q ) v = c (I-Q)v=c ( I − Q ) v = c v = N c v=Nc v = N c 1.25 × 2 + 0.625 × 5 = 5.625 1.25\times2+0.625\times5=5.625 1.25 × 2 + 0.625 × 5 = 5.625 v 1 = 2 + 0.5 v 2 v_1=2+0.5v_2 v 1 = 2 + 0.5 v 2 v 2 = 5 + 0.4 v 1 v_2=5+0.4v_1 v 2 = 5 + 0.4 v 1 N 1 N\mathbf1 N 1
非吸收链也可以写首达方程，但要小心：目标可能以小于 1 的概率到达，期望首达时间可能是无穷大；不能因为方程有一个形式解，就自动声称目标必达或期望有限。有限闭类结构和首达概率边界必须先判断。例如正文模型若只把 { 3 } \{3\} { 3 } 0.25 0.25 0.25 E 1 [ τ { 3 } ] = ∞ \mathbb E_1[\tau_{\{3\}}]=\infty E 1 [ τ { 3 } ] = ∞ 1.875 1.875 1.875 { 0 , 3 } \{0,3\} { 0 , 3 } m m m ∑ n = 0 m − 1 P i ( τ A > n ) \sum_{n=0}^{m-1}\mathbb P_i(\tau_A>n) ∑ n = 0 m − 1 P i ( τ A > n ) m m m E i τ A \mathbb E_i\tau_A E i τ A 0 ⋅ ∞ 0\cdot\infty 0 ⋅ ∞
先把目标设为 { 0 , 3 } \{0,3\} { 0 , 3 } { 2 } \{2\} { 2 } ( 2 , 5 ) (2,5) ( 2 , 5 )
路径有先后要求时，把必要的历史留下 仍用正文的四状态链，从 1 出发，改问“在吸收到 3 之前，是否已经经过状态 2”。直接走 1→3 虽然成功到达 3，却不符合这次的顺序要求。单独记录当前状态 1 还不够：一直没到过 2 时，和已经走过 1→2→1 时，后续成功事件的条件不同。
加入一个标记，记录“是否访问过 2”。标记为 1 之后不再擦掉，这时最终到 3 的成功概率就是前面算过的 h 1 = 0.75 , h 2 = 0.9 h_1=0.75,h_2=0.9 h 1 = 0.75 , h 2 = 0.9 g 1 g_1 g 1
g 1 = 0.2 × 0 + 0.5 h 2 + 0.3 × 0 = 0.45. g_1=0.2\times0+0.5h_2+0.3\times0=0.45. g 1 = 0.2 × 0 + 0.5 h 2 + 0.3 × 0 = 0.45. 把当前状态和访问标记合起来，便能用同样的首步方程处理新问题。扩张状态并不意味着一定要把完整历史保存下来；本题只需要一个是或否的记录。如果原图中所有到 3 的路径本来就必须经过 2，额外的顺序条件便没有筛掉任何路径，这时两事件反而相同。练习里会让你检查这种情形。
自测与练习 1 若 h_i 表示从 i 出发最终到达目标集合 A 的概率，i∈A 时的边界值是什么？
A. h_i=i B. 必须由矩阵幂决定 C. h_i=0 D. h_i=1
2 关于吸收链的基本矩阵 N=(I−Q)^{-1}，下列哪些说法正确？
3 只要状态 i 可以到达目标 j，就一定有从 i 出发最终到达 j 的概率 1。
巩固：写出首步方程
状态 0 是吸收目标，状态 1 每步以 0.3 到 0、以 0.7 留在 1。令 h i h_i h i h 1 h_1 h 1
查看解答 边界为 h 0 = 1 h_0=1 h 0 = 1 h 1 = 0.3 h 0 + 0.7 h 1 h_1=0.3h_0+0.7h_1 h 1 = 0.3 h 0 + 0.7 h 1 0.3 h 1 = 0.3 0.3h_1=0.3 0.3 h 1 = 0.3 h 1 = 1 h_1=1 h 1 = 1
若目标集合为 A = { 2 , 3 } A=\{2,3\} A = { 2 , 3 } h 1 = P 1 ( τ A < ∞ ) h_1=\mathbb P_1(\tau_A<\infty) h 1 = P 1 ( τ A < ∞ ) h 2 , h 3 h_2,h_3 h 2 , h 3
查看解答 因为 2、3 已在目标集合中，边界为 h 2 = h 3 = 1 h_2=h_3=1 h 2 = h 3 = 1 h 1 = 0.2 h 1 + 0.5 × 1 + 0.3 × 1 = 0.2 h 1 + 0.8 h_1=0.2h_1+0.5\times1+0.3\times1=0.2h_1+0.8 h 1 = 0.2 h 1 + 0.5 × 1 + 0.3 × 1 = 0.2 h 1 + 0.8
变式：分类与周期
某链的状态图中只有边 1→2、2→1、2→3、3→3、4→4，且每条列出的边概率均为正，未列出的边概率为 0。找出沟通类、闭类，并判断状态 1、3、4 的常返/暂态性质。
查看解答 沟通类是 { 1 , 2 } \{1,2\} { 1 , 2 } { 3 } \{3\} { 3 } { 4 } \{4\} { 4 } { 1 , 2 } \{1,2\} { 1 , 2 } { 3 } \{3\} { 3 } { 4 } \{4\} { 4 }
一个状态只能在 2、4、6、… 步返回，但也确实存在 2 步和 4 步返回。它的周期是多少？如果又发现存在 3 步返回，周期会怎样改变？
查看解答 只有偶数步返回时，可能返时时刻的最大公因数是 gcd ( 2 , 4 , 6 , … ) = 2 \gcd(2,4,6,\ldots)=2 g cd( 2 , 4 , 6 , … ) = 2 gcd ( 2 , 3 , 4 , … ) = 1 \gcd(2,3,4,\ldots)=1 g cd( 2 , 3 , 4 , … ) = 1
迁移：两种边界与期望时间
一条链的内部状态为 1、2，吸收态为 0、3，且
Q = ( 0.3 0.4 0.2 0.5 ) , R = ( 0.3 0 0 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}, Q = ( 0.3 0.2 0.4 0.5 ) , R = ( 0.3 0 0 0.3 ) , 其中吸收态顺序为 ( 0 , 3 ) (0,3) ( 0 , 3 )
查看解答 先算 I − Q = ( 0.7 − 0.4 − 0.2 0.5 ) I-Q=\begin{pmatrix}0.7&-0.4\\-0.2&0.5\end{pmatrix} I − Q = ( 0.7 − 0.2 − 0.4 0.5 ) 0.35 − 0.08 = 0.27 0.35-0.08=0.27 0.35 − 0.08 = 0.27
N = ( I − Q ) − 1 = 1 0.27 ( 0.5 0.4 0.2 0.7 ) . N=(I-Q)^{-1}=\frac1{0.27}\begin{pmatrix}0.5&0.4\\0.2&0.7\end{pmatrix}. N = ( I − Q ) − 1 = 0.27 1 ( 0.5 0.2 0.4 0.7 ) . 吸收概率矩阵 B = N R B=NR B = N R B 1 , 3 = 0.4 0.27 × 0.3 = 4 9 ≈ 0.4444 B_{1,3}=\frac{0.4}{0.27}\times0.3=\frac{4}{9}\approx0.4444 B 1 , 3 = 0.27 0.4 × 0.3 = 9 4 ≈ 0.4444 t 1 = ( N 1 ) 1 = 0.5 + 0.4 0.27 = 10 3 ≈ 3.3333 t_1=(N\mathbf1)_1=\frac{0.5+0.4}{0.27}=\frac{10}{3}\approx3.3333 t 1 = ( N 1 ) 1 = 0.27 0.5 + 0.4 = 3 10 ≈ 3.3333
对第 5 题，比较“最终到 3”和“先经过 2，再最终到 3”两事件。从 1 出发时它们相同吗？随后只把 R R R ( 0.1 , 0.2 ) (0.1,0.2) ( 0.1 , 0.2 ) Q Q Q R R R
查看解答 原模型中状态 1 没有直接到 3 的边，进入 3 的最后一步必从 2 出发，因此两事件相同，概率都是 4 / 9 4/9 4/9
修改后新增了从 1 直接到 3 的机会，两事件才分开。普通成功概率满足 h 1 = 0.3 h 1 + 0.4 h 2 + 0.2 h_1=0.3h_1+0.4h_2+0.2 h 1 = 0.3 h 1 + 0.4 h 2 + 0.2 h 2 = 0.2 h 1 + 0.5 h 2 + 0.3 h_2=0.2h_1+0.5h_2+0.3 h 2 = 0.2 h 1 + 0.5 h 2 + 0.3 h 1 = 22 / 27 , h 2 = 25 / 27 h_1=22/27,h_2=25/27 h 1 = 22/27 , h 2 = 25/27 g 1 = 0.3 g 1 + 0.4 h 2 g_1=0.3g_1+0.4h_2 g 1 = 0.3 g 1 + 0.4 h 2 g 1 = 100 / 189 g_1=100/189 g 1 = 100/189 22 / 27 − 100 / 189 = 2 / 7 22/27-100/189=2/7 22/27 − 100/189 = 2/7 0.2 / ( 1 − 0.3 ) 0.2/(1-0.3) 0.2/ ( 1 − 0.3 )
沿用第 5 题的 Q Q Q 50 / 27 50/27 50/27 40 / 27 40/27 40/27
查看解答 由已算的 N N N 50 / 27 , 40 / 27 50/27,40/27 50/27 , 40/27 2 ( 50 / 27 ) + 5 ( 40 / 27 ) = 100 / 9 2(50/27)+5(40/27)=100/9 2 ( 50/27 ) + 5 ( 40/27 ) = 100/9
状态 0、2 各自吸收，状态 1 一步到 0、1、2 的概率依次为 0.2 , 0.5 , 0.3 0.2,0.5,0.3 0.2 , 0.5 , 0.3
查看解答 方程是 h 2 = 1 h_2=1 h 2 = 1 h 0 = h 0 h_0=h_0 h 0 = h 0 h 1 = 0.2 h 0 + 0.5 h 1 + 0.3 h_1=0.2h_0+0.5h_1+0.3 h 1 = 0.2 h 0 + 0.5 h 1 + 0.3 h 1 = 0.4 h 0 + 0.6 h_1=0.4h_0+0.6 h 1 = 0.4 h 0 + 0.6 h 0 = 0 h_0=0 h 0 = 0 h 1 = 0.6 h_1=0.6 h 1 = 0.6 0.4 0.4 0.4 { 0 , 2 } \{0,2\} { 0 , 2 } t 1 = 1 + 0.5 t 1 t_1=1+0.5t_1 t 1 = 1 + 0.5 t 1
四状态链只有这些正概率边：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 } \{A,C\} { A , C } { B , D } \{B,D\} { B , D } gcd ( 2 , 3 ) = 1 \gcd(2,3)=1 g cd( 2 , 3 ) = 1
