02 离散时间马尔可夫链：从一步规则到矩阵演化 地铁站里的人流、服务器的负载、棋盘上的棋子，都可以在每一个离散时刻记录成一个状态。真正有用的问题不是“下一步有哪些可能”，而是：给定现在，下一步各自有多大概率？走很多步以后会在哪里？一开始的分布如何影响后来？
本章把上一章的条件概率压缩成转移矩阵，推导矩阵乘法为什么正好代表路径求和，再用同一套语言计算多步分布、路径概率和长期分布。这里的链指离散时间马尔可夫链：状态在 n = 0 , 1 , 2 , … n=0,1,2,\ldots n = 0 , 1 , 2 , …
定义与转移矩阵 设 S S S X 0 , X 1 , … X_0,X_1,\ldots X 0 , X 1 , … S S S n n n
P ( X n + 1 = j ∣ X 0 = i 0 , … , X n = i ) = P ( X n + 1 = j ∣ X n = i ) , \mathbb P(X_{n+1}=j\mid X_0=i_0,\ldots,X_n=i)
=\mathbb P(X_{n+1}=j\mid X_n=i), P ( X n + 1 = j ∣ X 0 就称它是马尔可夫链。若右侧不随 n n n
p i j = P ( X n + 1 = j ∣ X n = i ) , p_{ij}=\mathbb P(X_{n+1}=j\mid X_n=i), p ij = P ( X n + 1 = j ∣ X 则称为时间齐次马尔可夫链。以下默认时间齐次；若某状态在当前初始分布下根本不会出现，从它出发的转移规则仍可作为模型的一部分指定，但不能用概率为零的条件事件直接作除法来估计它。
对有限状态空间 S = { 1 , … , m } S=\{1,\ldots,m\} S = { 1 , … , m }
P = ( p i j ) m × m . P=(p_{ij})_{m\times m}. P = ( p ij ) m × m . 它必须满足两条检查：每个 p i j ≥ 0 p_{ij}\ge 0 p ij ≥ 0
∑ j = 1 m p i j = 1. \sum_{j=1}^m p_{ij}=1. j = 1 ∑ m p ij = 1. 行表示“从哪里出发”，列表示“到哪里去”。这是约定，不要在计算中把行列方向临时交换。
如果某一行只有一个非零元素，说明从该状态出发下一步被确定；如果 p i i = 1 p_{ii}=1 p ii = 1 i i i
从状态图读矩阵 状态图用有向边表示可能的一步转移，边上的数字是概率。没有画出的边通常表示概率 0。比如三状态链 S = { A , B , C } S=\{A,B,C\} S = { A , B , C }
P = ( 0.5 0.5 0 0.2 0.5 0.3 0 0.4 0.6 ) . P=
\begin{pmatrix}
0.5&0.5&0\\
0.2&0.5&0.3\\
0&0.4&0.6
\end{pmatrix}. P = 0.5 从 A A A A , B , C A,B,C A , B , C 0.5 , 0.5 , 0 0.5,0.5,0 0.5 , 0.5 , 0 C C C B , C B,C B , C 0.4
一步、两步与 n 步概率 记
p i j ( n ) = P ( X n = j ∣ X 0 = i ) . p_{ij}^{(n)}=\mathbb P(X_n=j\mid X_0=i). p ij ( n ) = P ( X n = j ∣ 这里也可把起点固定为 i i i i i i p i j ( 0 ) p_{ij}^{(0)} p ij ( 0 ) i = j i=j i = j
p i j ( 2 ) = P ( X 2 = j ∣ X 0 = i ) = ∑ k ∈ S P ( X 1 = k ∣ X 0 = i ) P ( X 2 = j ∣ X 1 = k , X 0 = i ) = ∑ k ∈ S p i k p k j . \begin{aligned}
p_{ij}^{(2)}
&=\mathbb P(X_2=j\mid X_0=i)\\
&=\sum_{k\in S}\mathbb P(X_1=k\mid X_0=i)\mathbb P(X_2=j\mid X_1=k,X_0=i)\\
&=\sum_{k\in S}p_{ik}p_{kj}.
\end{aligned} p 第二行使用全概率公式按 X 1 = k X_1=k X 1 = k X 0 = i X_0=i X 0 = i p k j p_{kj} p
p i j ( 2 ) = ( P 2 ) i j . p_{ij}^{(2)}=(P^2)_{ij}. p ij ( 2 ) = ( P 2 ) ij . 走 n + r n+r n + r n n n k k k r r r k k k r r r k k
p i j ( n + r ) = ∑ k ∈ S p i k ( n ) p k j ( r ) , p_{ij}^{(n+r)}=\sum_{k\in S}p_{ik}^{(n)}p_{kj}^{(r)}, p ij ( n + r ) = k ∈ S ∑ 也就是
P n + r = P n P r . P^{n+r}=P^nP^r. P n + r = P n P r . 矩阵乘法不是记号上的巧合：每个乘积项代表“中途位于 k k k j j j
在刚才的 A , B , C A,B,C A , B , C A A A B B B 0.5 × 0.5 + 0.5 × 0.5 + 0 × 0.4 = 0.5 0.5\times0.5+0.5\times0.5+0\times0.4=0.5 0.5 × 0.5 + 0.5 × 0.5 +
可数无限状态时也按所有中间状态作非负求和；本章计算例题使用有限状态，避免把有限矩阵的数值运算直接套到无穷矩阵上。
计算 P n P^n P n i i i P n P^n P n i i i
从确定起点算两步分布 考虑状态空间 S = { 0 , 1 , 2 } S=\{0,1,2\} S = { 0 , 1 , 2 }
P = ( 0.6 0.4 0 0.1 0.6 0.3 0 0.2 0.8 ) , μ 0 = ( 1 , 0 , 0 ) . P=\begin{pmatrix}
0.6&0.4&0\\
0.1&0.6&0.3\\
0&0.2&0.8
\end{pmatrix},
\qquad \mu_0=(1,0,0). P = 求 μ 2 \mu_2 μ 2
初始状态已经确定，用 μ 0 P \mu_0P μ 0 P P P P
一步分布是
μ 1 = μ 0 P = ( 0.6 , 0.4 , 0 ) \mu_1=\mu_0P=(0.6,0.4,0) μ 1 = μ 0 P = ( 0.6 , 。这正是矩阵第 0 行，因为一开始确定在状态 0。分量和为 1，说明没有漏掉概率。
到状态 2 不等于“某一步曾经到过 2”。在这个例子里，前两步恰好还看不出区别，因为从 0 出发最快要两步才到 2。把问题延长到三步，差别就出现了，下面会把两种事件各算一次。
路径概率与事件概率 给定一段具体路径 i 0 , i 1 , … , i n i_0,i_1,\ldots,i_n i 0 , i 1 , … , i n
P ( X 0 = i 0 , … , X n = i n ) = P ( X 0 = i 0 ) ∏ r = 0 n − 1 p i r i r + 1 . \mathbb P(X_0=i_0,\ldots,X_n=i_n)
=\mathbb P(X_0=i_0)\prod_{r=0}^{n-1}p_{i_ri_{r+1}}. P ( X 0 = i 0 , … , 把联合概率写成“起点概率 × 第一步条件概率 × 给定前两时刻的第二步条件概率 × …”，再逐项使用马尔可夫性和时间齐次性，就得到这个式子。若给定 X 0 = i 0 X_0=i_0 X 0 = i 0 ( P n ) i j (P^n)_{ij} ( P n )
例如在上面的三状态链中，从 0 出发三步后到 2，可以按第二步状态分解：
P ( X 3 = 2 ∣ X 0 = 0 ) = p 00 ( 2 ) p 02 + p 01 ( 2 ) p 12 + p 02 ( 2 ) p 22 . \mathbb P(X_3=2\mid X_0=0)
=p_{00}^{(2)}p_{02}+p_{01}^{(2)}p_{12}+p_{02}^{(2)}p_{22}. P ( X 3 = 2 ∣ X 0 = 这不是把三步中的某一条路径重复相加，而是按互斥的第 2 步状态分组；每组内部已经包含了更早路径的总和。
代入两步分布，得到 0.40 × 0 + 0.48 × 0.3 + 0.12 × 0.8 = 0.24 0.40\times0+0.48\times0.3+0.12\times0.8=0.24 0.40 × 0 + 0.48 × 0.3 + 0.12 × 0.8 = 0.24
0 → 0 → 1 → 2 : 0.6 × 0.4 × 0.3 = 0.072 , 0 → 1 → 1 → 2 : 0.4 × 0.6 × 0.3 = 0.072 , 0 → 1 → 2 → 2 : 0.4 × 0.3 × 0.8 = 0.096. \begin{aligned}
0\to0\to1\to2 &: \quad0.6\times0.4\times0.3=0.072,\\
0\to1\to1\to2 &: \quad0.4\times0.6\times0.3=0.072,\\
0\to1\to2\to2 &: \quad0.4\times0.3\times0.8=0.096.
\end{aligned} 0 → 0 → 1 → 2 0 → 1 三项相加为 0.24 0.24 0.24 0 → 1 → 2 → 2 0\to1\to2\to2 0 → 1 → 2 → 2 0.096 0.096 0.096
若问“三步内至少到过一次 2”，还要收下 0 → 1 → 2 → 1 0\to1\to2\to1 0 → 1 → 2 → 1 0.4 × 0.3 × 0.2 = 0.024 0.4\times0.3\times0.2=0.024 0.4 × 0.3 × 0.2 = 0.024 0.24 + 0.024 = 0.264 0.24+0.024=0.264 0.24 +
实验从刚才的矩阵和 μ 0 = ( 1 , 0 , 0 ) \mu_0=(1,0,0) μ 0 = ( 1 , 0 , 0 ) 0.12 0.12 0.12 0.24 0.24 0.24 0.24 0.24 0.24 0.264 0.264
分布递推与平稳分布 若 μ n ( j ) = P ( X n = j ) \mu_n(j)=\mathbb P(X_n=j) μ n ( j ) = P ( X n = j ) j j j
μ n + 1 ( j ) = ∑ i ∈ S μ n ( i ) p i j . \mu_{n+1}(j)=\sum_{i\in S}\mu_n(i)p_{ij}. μ n + 1 ( j ) = i ∈ S ∑ μ n 写成行向量就是
μ n + 1 = μ n P . \mu_{n+1}=\mu_nP. μ n + 1 = μ n P . 平稳分布是一个概率行向量 π \pi π
π = π P , ∑ i π i = 1 , π i ≥ 0. \pi=\pi P,\qquad \sum_i\pi_i=1,\quad \pi_i\ge0. π = π P , i ∑ π i = 1 , π 如果 μ 0 = π \mu_0=\pi μ 0 = π μ n = π \mu_n=\pi μ n = π n n n
平稳时，仍有路径在移动 设两状态链 S = { A , B } S=\{A,B\} S = { A , B }
P = ( 0.7 0.3 0.4 0.6 ) . P=\begin{pmatrix}0.7&0.3\\0.4&0.6\end{pmatrix}. P = ( 0.7 0.4 0.3 0.6 ) . 求平稳分布 π = ( a , b ) \pi=(a,b) π = ( a , b )
状态只有两个，直接解 π = π P \pi=\pi P π = π P
由
π = π P \pi=\pi P π = π P 的第一列得到
a = 0.7 a + 0.4 b a=0.7a+0.4b a = 0.7 a + 0.4 b ，移项为
0.3 a = 0.4 b 0.3a=0.4b 0.3 a 。这条方程表达的是一步后回到 A 的概率必须等于原来在 A 的概率。
这条两状态链在平稳时，从 A 转到 B 的概率质量是 ( 4 / 7 ) ( 3 / 10 ) = 6 / 35 (4/7)(3/10)=6/35 ( 4/7 ) ( 3/10 ) = 6/35 ( 3 / 7 ) ( 2 / 5 ) = 6 / 35 (3/7)(2/5)=6/35 ( 3/7 ) ( 2/5 ) = 6/35
一般的平稳方程只要求每个状态收到的总量等于原有总量。若每对状态还满足 π i p i j = π j p j i \pi_i p_{ij}=\pi_j p_{ji} π i p ij = π j p j
把上图的蓝、橙、绿节点依次叫 A、B、C，每步沿箭头走，转移概率都为 1。此时 π = ( 1 / 3 , 1 / 3 , 1 / 3 ) \pi=(1/3,1/3,1/3) π = ( 1/3 , 1/3 , 1/3 ) 1 / 3 1/3 1/3 1 / 3 1/3 1/3
两状态链能把边界算清楚 将两状态矩阵写成
P = ( 1 − α α β 1 − β ) , 0 ≤ α , β ≤ 1. P=\begin{pmatrix}1-\alpha&\alpha\\\beta&1-\beta\end{pmatrix},
\qquad 0\le\alpha,\beta\le1. P = ( 1 − α β α 1 − β 设 q n = P ( X n = A ) q_n=\mathbb P(X_n=A) q n = P ( X n = A )
q n + 1 = ( 1 − α ) q n + β ( 1 − q n ) = β + ( 1 − α − β ) q n . q_{n+1}=(1-\alpha)q_n+\beta(1-q_n)
=\beta+(1-\alpha-\beta)q_n. q n + 1 = ( 1 − α ) q n + 若 α + β > 0 \alpha+\beta>0 α + β > 0 π A = β / ( α + β ) \pi_A=\beta/(\alpha+\beta) π A = β / ( α + β )
q n + 1 − π A = ( 1 − α − β ) ( q n − π A ) . q_{n+1}-\pi_A=(1-\alpha-\beta)(q_n-\pi_A). q n + 1 − π A = ( 1 − α − 反复代入就有
q n = π A + ( 1 − α − β ) n ( q 0 − π A ) . q_n=\pi_A+(1-\alpha-\beta)^n(q_0-\pi_A). q n = π A + ( 1 − α − β 当 0 < α + β < 2 0<\alpha+\beta<2 0 < α + β < 2 π \pi π
端点不能顺手省去。若 α = β = 0 \alpha=\beta=0 α = β = 0 P = I P=I P = I α = β = 1 \alpha=\beta=1 α = β = 1 ( 1 / 2 , 1 / 2 ) (1/2,1/2)
一步模型的诊断与常见错误 一个矩阵看起来像概率矩阵，还不代表它适合某个现实问题。至少检查：状态是否互斥且覆盖了观察对象；时间步长是否一致；转移概率是否确实只依赖当前状态；矩阵是否随时间改变；观测数据是否把多个真实状态压成了一个含糊标签。
常见计算错误有三种。第一，把 P 2 P^2 P 2 P μ P\mu P μ
如果一次修改只改变矩阵某个元素，却不调整同一行的其他元素，行和可能不再等于 1。概率转移不是一组互不相关的旋钮：从同一个状态出发的所有去向必须共同分配总概率 1。任何矩阵幂、平稳方程或模拟结果之前，都先做非负性和行和检查。
恢复 α = 0.3 , β = 0.4 \alpha=0.3,\beta=0.4 α = 0.3 , β = 0.4 q n q_n q n 4 / 7 4/7 4/7 1 / 2 1/2 1/2
自测与练习 1 若分布采用行向量约定，初始分布 μ₀ 经过一步后的分布是什么？
A. Pμ₀ B. P^{-1}μ₀ C. μ₀P D. μ₀+P
3 如果初始分布就是平稳分布，那么每一步的边缘分布都等于这个平稳分布。
巩固：矩阵与两步概率
给定
P = ( 0.8 0.2 0.5 0.5 ) , P=\begin{pmatrix}0.8&0.2\\0.5&0.5\end{pmatrix}, P = ( 0.8 0.5 0.2 0.5 ) , 计算从状态 1 出发两步后回到状态 1 的概率，并列出按中间状态分解的两项。
查看解答 按第 1 步中间状态 1 或 2 分解，概率为 p 11 p 11 + p 12 p 21 = 0.8 × 0.8 + 0.2 × 0.5 = 0.74 p_{11}p_{11}+p_{12}p_{21}=0.8\times0.8+0.2\times0.5=0.74 p 11 p 11 + p 12 p
某链的初始分布为 μ 0 = ( 0.2 , 0.5 , 0.3 ) \mu_0=(0.2,0.5,0.3) μ 0 = ( 0.2 , 0.5 , 0.3 ) ( 0.1 , 0.6 , 0.3 ) (0.1,0.6,0.3) ( 0.1 , 0.6 , 0.3 ) μ 1 \mu_1 μ
查看解答 只需要每个出发状态到目标状态 1 的概率，也就是矩阵第一列；题目只给出第一行，因此信息还不完整。若补充第一列为 ( 0.1 , 0.2 , 0.4 ) T (0.1,0.2,0.4)^\mathsf T ( 0.1 , 0.2 , 0.4 ) T μ 1 ( 1 ) = 0.2 × 0.1 + 0.5 × 0.2 + 0.3 × 0.4 = 0.24 \mu_1(1)=0.2\times0.1+0.5\times0.2+0.3\times0.4=0.24 μ 1 ( 1 ) = 0.2 ×
变式：路径与终点事件
从状态 A 出发，三步后位于 C 的事件包含路径 A→B→B→C 和 A→A→B→C。解释为什么不能只把这两条路径相加就宣称得到三步到 C 的完整概率，并写出正确的计算思路。
查看解答 这两条路径只是所有可能三步路径中的两条，其他中间状态序列也可能在 C 结束。正确做法是对所有 i 1 , i 2 ∈ S i_1,i_2\in S i 1 , i 2 ∈ S P ( X 3 = C ∣ X 0 = A ) = ∑ i 1 , i 2 p A i 1 p i 1 i 2 p i 2 C \mathbb P(X_3=C\mid X_0=A)=\sum_{i_1,i_2}p_{Ai_1}p_{i_1i_2}p_{i_2C}
对同一个转移矩阵，初始分布改为另一个向量，平稳分布会不会必然改变？请说明判断理由。
查看解答 固定 P P P π = π P \pi=\pi P π = π P μ n = μ 0 P n \mu_n=\mu_0P^n μ n = μ 0
迁移：选择计算方式并解释结果
一台服务器有“空闲、忙、过载”三种状态。每天状态更新一次，转移矩阵为
P = ( 0.6 0.4 0 0.2 0.6 0.2 0 0.3 0.7 ) , μ 0 = ( 0.5 , 0.5 , 0 ) . P=\begin{pmatrix}0.6&0.4&0\\0.2&0.6&0.2\\0&0.3&0.7\end{pmatrix},
\quad \mu_0=(0.5,0.5,0). P = 求一天后的分布，并计算两天后处于过载的概率。请说明你会用分布递推还是完整矩阵幂，以及为什么。
查看解答 用分布递推更合适，因为只需一个初始分布和一个目标分量，不必先求整个 P 2 P^2 P 2 μ 1 = μ 0 P = ( 0.4 , 0.5 , 0.1 ) \mu_1=\mu_0P=(0.4,0.5,0.1) μ 1 = μ 0 P = (
某转移矩阵的两个状态集合互不相通，并且每个集合内部都有自己的平稳分布。说明为什么把两个集合内的平稳分布按非负权重混合，仍得到整个链的平稳分布；这对“长期分布唯一”有什么提醒？
查看解答 设 π ( 1 ) P = π ( 1 ) \pi^{(1)}P=\pi^{(1)} π ( 1 ) P = π ( 1 ) π ( 2 ) P = π ( 2 ) \pi^{(2)}P=\pi^{(2)} π ( 2 )
对两状态链，已知平稳时处于 A 的概率为 3 / 4 3/4 3/4 1 / 5 1/5 1/5 α , β \alpha,\beta α , β q 0 = 1 / 4 q_0=1/4 q 0 = 1/4 q 2 q_2
查看解答 从误差递推读出 1 − α − β = 1 / 5 1-\alpha-\beta=1/5 1 − α − β = 1/5 α + β = 4 / 5 \alpha+\beta=4/5 α + β = 4/5 β / ( α + β ) = 3 / 4 \beta/(\alpha+\beta)=3/4 β
两状态链的转移矩阵是
P = ( 0.5 0.5 1 0 ) , μ 0 = ( 0.4 , 0.6 ) , P=\begin{pmatrix}0.5&0.5\\1&0\end{pmatrix},\qquad \mu_0=(0.4,0.6), P = ( 0.5 1 0.5 0 ) , μ 状态顺序为 A、B。计算指定路径 A→B→A 的概率，以及给定从 A 出发时这条路径的条件概率。再比较“第 2 步在 B”与“从第 0 步到第 2 步至少在 B 一次”的概率。后一事件包括初始时刻。
查看解答 指定路径的概率是 0.4 × 0.5 × 1 = 0.2 0.4\times0.5\times1=0.2 0.4 × 0.5 × 1 = 0.2 0.5 0.5 0.5 μ 1 = ( 0.8 , 0.2 ) \mu_1=(0.8,0.2) μ 1 = ( 0.8 , 0.2
三状态链每步以 1 / 2 1/2 1/2 1 / 2 1/2 1/2
查看解答 矩阵为
P = ( 1 / 2 1 / 2 0 0 1 / 2 1 / 2 1 / 2 0 1 / 2 ) . P=\begin{pmatrix}1/2&1/2&0\\0&1/2&1/2\\1/2&0&1/2\end{pmatrix}. P = 
