10-2-Markov矩阵与稳态
一句话概括
随机矩阵(Markov matrix) 是"元素非负、每列和为 "的方阵。它的第 列是一个概率分布,而 把第 步的概率分布映成第 步的概率分布。由"每列和为 "立刻得到 ,即 一定是特征值;对应的特征向量 满足 ,就是稳态(steady state)。幂迭代 收敛到稳态的充要条件是"除 外其余特征值的模都小于 "——这解释了为什么周期链会不收敛,也是 PageRank 必须引入阻尼因子的原因。
本篇覆盖:随机矩阵的定义与"为什么按列",状态转移的建模,稳态的定义与存在性证明,Perron–Frobenius 定理的完整表述与直观解释,收敛性的充要条件(含周期链反例),一个 状态的完整数值例题(求 、求特征值、求稳态、迭代验证收敛),PageRank 的核心思想(阻尼因子 、悬挂节点、稀疏性),一段可运行的 numpy 代码(构造随机矩阵、幂迭代求稳态、用特征值预测收敛速度),以及人口迁移、市场份额、排队模型等应用。
这一章是"特征值理论 + 应用"最漂亮的一次会面:矩阵的幂、特征值的模、马尔可夫链的长期行为,三件事说的是同一件事。
一、定义
1.1 随机矩阵是"把概率分布映成概率分布"的矩阵
定义 10.3.1(随机矩阵,Markov matrix / stochastic matrix) 设 是 实矩阵。若满足
- 非负性: 对一切 ;
- 每列和为 : 对每个 成立,
则称 为随机矩阵(也叫马尔可夫矩阵、列随机矩阵)。
第 列就是一个概率分布: 表示"当前处于状态 时,下一步转移到状态 的概率"。写成矩阵:
(意思是:第一列的各分量之和为 ,第二列、第三列……同样如此。)
1.2 为什么是"每列和为 ",而不是每行和为
这个问题的答案只有一句话:因为 是从左边乘在分布向量上的
我们规定状态转移方程为
其中 是第 步的概率分布向量(分量为非负、总和为 )。
既然 写在 的右边,那么"把分布映成分布"这件事就必须由 的列来保证。验证一下:设 是非负向量且 (),计算新向量的分量之和:
中间那一步用到的正是",即 的每列和为 "。同时 的分量非负(非负矩阵乘非负向量),所以 仍是概率分布 ✓。
反过来,若 每行和为 (即 ),则 ,一般不等于 ——分布会被"弄丢总和",不再是一个概率分布。
另一种等价说法:如果习惯把分布写成行向量 并规定 (很多概率教材是这种写法),那么 就必须是"每行和为 "。两种写法互为转置,数学内容完全相同。本篇(与 Strang 教材一致)统一采用
判断一个矩阵是不是随机矩阵的最快方法:把它每一列加起来,看是否都等于 。
1.3 "每列和为 "的矩阵语言:
把"每列和为 "写成矩阵等式,就是
两边转置,得到本篇第一个关键结论:
这是一句"特征值宣言": 有特征值 ,特征向量是 。而 与 的特征多项式相同(因为 ),所以 也一定有特征值 。这就是" 一定是特征值"的完整理由,1.5 节会把它写成定理。
一个极易混淆的细节
说的是: 是 的特征向量(对应特征值 ),也就是" 的左特征向量"。
它不是" 是 的稳态"!稳态 满足 ,这是 的右特征向量,一般 (例如 4.1 节的例题里稳态是 ,而 )。
一句话区分: 保证"稳态存在", 给出"稳态是什么"。
1.4 稳态的定义
定义 10.3.2(稳态分布,steady state) 设 是随机矩阵。若非零向量 满足
则称 为 的一个稳态分布(或平稳分布)。通常再把它规范化,使各分量之和为 (),使它成为一个真正的概率分布。
为什么叫"稳态":若 ,则 ,分布不再随时间改变——系统"静止"了。按特征值的语言, 就是特征值 的特征向量。
定义 10.3.3(周期性)
若 是随机矩阵且存在正整数 使 (即"走 步必然回到原状态"),则称该链是周期的(periodic)。周期链的转移概率不会"忘记初值",往往导致 不收敛。4.3 节给出具体反例。
1.5 存在性: 一定是特征值
定理 10.3.1(随机矩阵必有特征值 )
设 是 随机矩阵,则 是 的特征值,且 有特征向量 。
证明(两步,都很短)
第一步:。
由随机矩阵的定义, 的每列和为 。而" 的第 列之和"就是" 的第 行与 的点积",所以
即 ,说明 是 的特征值(特征向量 )。
第二步: 与 有相同的特征值。
对任意 ,
因为转置不改变行列式(见 5-1-行列式的性质)。两个矩阵的特征多项式完全相同,特征值自然相同。第一步已知 是 的特征值,故 也是 的特征值。
这一定理的两层含义
1. 存在性:随机矩阵的稳态( 的特征向量)一定存在——只要它不是零向量。严格地说, 等价于 ,而 (因为 是特征值),所以 至少一维,一定有非零解。
2. "左零空间的对应物":在 10-1-图与网络 里,关联矩阵满足 (每列和为 )——那是" 有一个被钉死的特征值 , 是它的特征向量"。这里把 换成 ,同一个代数事实就变成了"左特征向量 保证右特征向量(稳态)存在"。" 型恒等式"永远在告诉你"某个特征值被钉死了": 时钉住 , 时钉住 。
1.6 唯一性需要什么条件
上一定理只保证存在。要保证唯一(并且在规范化为概率分布时唯一),需要更强的条件。先把最一般的结论列清楚:
- 若链不可约(irreducible,从任何状态都能到达任何状态,即转移图强连通)且非周期,则随机矩阵 有唯一的稳态分布 ,且对任意初始分布 都有 。
- 若链不可约但周期,则稳态仍唯一,但 不收敛(会在若干分布之间轮转)。
- 若链可约(例如有两个互不相通的封闭状态集),则稳态不唯一,极限取决于初值 。
这些结论的严格证明属于随机过程课程;本篇的重点是用特征值把它们统一解释清楚(3.3 节)。
二、几何直观
2.1 概率分布向量的几何: 中的一个单纯形
所有概率分布(、)构成 中的单纯形(simplex):
- :从 到 的线段;
- :顶点为 、、 的三角形;
- 一般 : 维的凸多面体。
随机矩阵 的作用,就是把这个单纯形映到它自己。 这是一个"几何上自我封闭"的线性映射——它不放大也不缩小这个集合,只让分布在其中"流动"。 就是在这个单纯形里一步一步地走。
三个直观画面
1. 流动画面:把 想成"第 个城市的人口比例", 是"第 城迁往第 城的比例"。一年后比例变成 。稳态就是"每年迁入迁出恰好平衡"的人口结构。
2. 混合画面:如果 的每一列都相同(例如每列都等于 ),那么 对任何 成立——一步就到稳态,完全不记得初值。这种矩阵秩为 (见 3-5-四大子空间的维数)。
3. 特征值画面: 可以按 的特征向量展开:
于是
因为 ,第一项 永远不变(这就是稳态成分);而其余项带着 衰减。"收敛"的几何图像就是:所有非稳态成分被逐步压缩到零,只剩下那个不动的分量。 详见 6-2-矩阵的对角化。
2.2 为什么"列和"这个条件如此有力
一个 矩阵有 个自由度,而"每列和为 "只给了 个约束——看似不多,但它一下子钉死了两件事:
- 存在: ⟹ 是特征值 ⟹ 稳态存在;
- 有界: 的每个元素 ,所以 的元素也 (非负矩阵乘非负矩阵仍然非负,且列和保持为 )。这让幂迭代 在数值上绝不会发散——这是幂迭代能作为求稳态的实用算法的根本原因。
一个必看的推论: 也是随机矩阵
若 、 都是随机矩阵,则 也是:非负显然; 的列和 ✓。归纳得 对一切 都是随机矩阵。
物理含义: 的第 列就是"从状态 出发、走 步后的分布"。所以 确实是"走 步"的结果。
2.3 稳态的几何含义:单纯形的不动点
把单纯形映到自身,把这个连续映射的不动点()称为稳态。由 Brouwer 不动点定理这类拓扑论证可知它一定存在;但在随机矩阵的场合,我们有一个纯代数的证明(定理 10.3.1),不需要拓扑学。
几何上,稳态是"流动的平衡点":流进每个状态的"概率质量"恰好等于流出的。写成方程(对分量 求和):
(下面括号里分别是"从其他状态流入"与"留在原地"两项。)
把它整理一下就是"流入 = 流出":
这与 10-1-图与网络 里的基尔霍夫电流定律(KCL)是同一个方程的形状——稳态分布就是"概率质量上的无源无汇流"。
三、性质与定理
3.1 Perron–Frobenius 定理
定理 10.3.2(Perron–Frobenius,正矩阵情形)
设 是 矩阵,且所有元素都严格为正()。则:
1. 有一个正实数特征值 ,且对 的任何其他特征值 都有 ( 是严格占优的,称为 Perron 根);
2. 对应 的特征向量可以取为全正向量(每个分量 );
3. 的代数重数为 (特征空间是一维的),因此这个正特征向量在相差一个正常数倍的意义下唯一。
对随机矩阵的特殊化(本篇最常用的版本):
推论 10.3.3(正随机矩阵的 Perron–Frobenius)
若 是正随机矩阵( 且每列和为 ),则
且稳态分布 唯一、全正,并且对任意初始分布 有
为什么此时 :由定理 10.3.1, 是特征值;由 Perron–Frobenius,模最大的特征值 唯一且为正。于是只需排除 。而这很容易:随机矩阵的谱半径不超过 ,因为对任意特征对 ,取分量中模最大者 ,则
两边除以 得 。于是模最大的特征值只能是 ,即 ,而 Perron–Frobenius 保证其余 。
Perron–Frobenius 的直观解释(三句话)
1. "全正"意味着"人人都能直接到人人": 表示从 一步就能到 ,没有任何"孤岛"或"单向门"。这种彻底的连通性排除了两个稳态并存(那需要两个互不相通的封闭集合)。
2. "模最大特征值唯一"意味着"只有一种长期行为":如果还有另一个特征值的模也等于 (比如 ),那么 里就会留下一个永不衰减的成分,系统会永远"晃"下去(这正是周期性)。
3. "正特征向量"意味着"稳态不排斥任何状态":每个状态在长期中都会被访问,概率严格为正。
一句话:Perron–Frobenius 说的是"彻底的连通性 ⟹ 唯一的长期平衡"。它与 10-1-图与网络 中"图连通 ⟺ 拉普拉斯矩阵零特征值重数为 "是同一种精神:连通性就是"零空间/特征空间变小"。
3.2 一般随机矩阵的谱半径与
定理 10.3.4(随机矩阵的谱性质)
设 是随机矩阵(不要求正)。则
1. 对一切特征值成立,即谱半径(spectral radius) ;
2. 若 的某个特征值满足 ,则 必是单位根(即 对某个正整数 成立),此时链是周期的;
3. 特别地, 的所有特征值都满足 ,且 至少是一个特征值(定理 10.3.1)。
证明(第 1 条) 就是上面用过的"取模最大分量"论证:对特征对 ,设 ,则
适用条件与说明:第 1 条只用到"非负 + 每列和为 ",不要求正。第 2 条的严格证明需要 Perron–Frobenius 理论的完整版本(非负矩阵情形),这里作为结论使用。
3.3 收敛性:幂迭代何时收敛
这是本篇最核心的定理,也是 PageRank 能工作的全部理由。
定理 10.3.5(幂迭代的收敛判据)
设 是随机矩阵,特征值为 (按重数计)。若
(且 的代数重数等于几何重数,即 可对角化),则对任意初始分布 ,都有
其中 由 在稳态方向上的分量决定。特别地,若 已是概率分布且稳态规范化为 ,则 ,极限就是稳态分布本身。
反之,若存在某个 使 ,则一般不收敛。
证明 设 可对角化,, 的列是特征向量 (取 对应 ),。把 按这组基展开:
由 (见 6-2-矩阵的对角化),以及 :
由于 ,每一项 (),故
若存在某个 使 ,则 不趋于 ,对应的成分 永不消失(除非恰好 ,即初值"碰巧"没有这个成分),故一般不收敛。
收敛速度由"第二大特征值"决定
误差满足
也就是说:每迭代一步,误差大约乘以 。定义收敛速率(convergence rate)为 (有时用 表示"每步获得的有效位数")。
- 越接近 ,收敛越快( 时一步到位);
- 越接近 ,收敛越慢(PageRank 里 ,每步只消掉约 的误差,所以需要几十次迭代);
- 时完全不收敛(周期链)。
3.4 周期链为什么不收敛:反例
例(最简单的周期链)
分析 的每列和都是 ✓(非负 ✓),是随机矩阵。特征值:,故
的模等于 ,违背定理 10.3.5 的条件。看迭代:
它在两个分布之间永远振荡,不收敛。 物理含义:这个链只有两个状态,且必然来回跳(概率 地 、),所以"第 步在哪个状态"完全由奇偶性决定,任何初值信息都不会被"忘记"。
但稳态仍然存在(这是关键的一点): 即
所以"稳态存在"与"幂迭代收敛"是两回事:前者只要求 是特征值(一定成立),后者要求其余特征值的模都严格小于 。
验证"平均意义下的收敛":虽然 不收敛,但
右边这个向量就是稳态 。
这叫Cesàro 收敛(平均收敛)。它解释了一个常见现象:周期链的"时间平均"仍然给出正确的长期频率——只是瞬时的 永远在晃。
一个极其常见的误解
很多人以为"随机矩阵一定有稳态,所以幂迭代一定收敛"。错。 正确的逻辑是:随机矩阵 ⟹ 是特征值 ⟹ 稳态存在(这是必然的);但幂迭代收敛另有条件:
前者是必然,后者是额外条件。周期链(如 、)就是反例。
3.5 稳态与初值无关的条件
"幂迭代收敛到稳态"这句话里的极限 中, 一般依赖初值 。要让极限与初值无关(即无论从哪里出发都到同一个分布),需要 的代数重数为 且其余 。
- 若 的转移图强连通(不可约),则 ( 是单重特征值), 由规范化为概率分布唯一确定;
- 若 可约,例如
则 是二重特征值,任何 都是稳态(),极限完全取决于初值:从 出发永远停在 ,从 出发永远停在 。
这也是 PageRank 要引入阻尼因子的第二个原因(第一个是处理悬挂节点): 这一项让矩阵全正,从而自动满足" 单重 + 其余 ",极限与初值无关、且唯一。
四、计算方法与步骤
4.1 求稳态的三种方法
方法一:解线性方程组(精确解,推荐手算)
稳态满足 ,即 是 中的非零向量。取 的基向量,再按"分量之和为 "规范化。
步骤:
- 写出 ;
- 对它做行化简,求零空间的一组基;
- 把基向量按比例缩放,使其各分量之和为 (若基向量有负分量,说明它不是合法的概率分布——那通常意味着 不满足本篇假设,需要检查)。
方法二:幂迭代(数值解,推荐大规模问题)
,反复迭代直到变化很小。收敛速率由 决定;误差按 衰减。
方法三:解增广方程组(数值上最稳的"直接法")
把 去掉一个冗余方程,换上规范化条件 :
(第一块是 的前 行,最后一行是规范化条件 。)
这是 个方程、 个未知数,且矩阵可逆(前提是 单重),可以直接解。本篇的 numpy 示例就用这一种。
4.2 判断收敛性与估计速度的四步
- 算 的全部特征值( 必有一个);
- 看除 外是否所有 :是 ⟹ 幂迭代收敛;否(存在 )⟹ 周期链,不收敛;
- 若收敛,收敛速率 (按模第二大者);
- 需要 精度时,迭代次数约 。
一个常用速算
时,,要 6 位有效数字()需 步。
时,,同样精度只需 步。
从 降到 ,迭代次数减少约 倍——这就是"收敛速率"的实际分量。
4.3 可运行的 numpy 例子
本示例只需 numpy(numpy.linalg 已提供 eig、matrix_rank、solve),无需额外安装。
import numpy as np
np.set_printoptions(precision=6, suppress=True)
# ---------- 1. 构造随机矩阵:每个状态按给定比例转到各状态 ----------
# 第 j 列 = 处于状态 j 时下一步的转移概率(列和必须为 1)
A = np.array([[0.4, 0.3, 0.3],
[0.2, 0.4, 0.4],
[0.4, 0.3, 0.3]])
print("列和:", A.sum(axis=0)) # 应全为 1
print("行和:", A.sum(axis=1)) # 一般不为 1(不要混淆!)
assert np.allclose(A.sum(axis=0), 1.0)
assert np.all(A >= 0)
# ---------- 2. 特征值:一定有 1,其余模应小于 1 ----------
w, V = np.linalg.eig(A)
print("特征值:", w)
print("模:", np.abs(w))
assert np.isclose(max(np.abs(w)), 1.0)
# 幂迭代的收敛速率 = 除 1 外模最大的特征值
mods = np.sort(np.abs(w))[::-1]
rate = mods[1]
print("收敛速率 |lambda_2| =", rate)
# ---------- 3. 求稳态:解增广方程组(直接法) ----------
n = A.shape[0]
M = np.vstack([A - np.eye(n), np.ones(n)])
b = np.append(np.zeros(n), 1.0)
# 用最小二乘解超定方程组(等价于"去掉一个冗余方程 + 规范化")
u_ss = np.linalg.lstsq(M, b, rcond=None)[0]
print("稳态 u =", u_ss, " 分量和 =", u_ss.sum())
print("检查 A u - u =", np.round(A @ u_ss - u_ss, 12))
# ---------- 4. 幂迭代:从不同初值出发都应到同一个稳态 ----------
for name, start in [("e1", np.array([1.0, 0, 0])),
("e2", np.array([0, 1.0, 0])),
("e3", np.array([0, 0, 1.0]))]:
u = start.copy()
print(f"--- 初值 {name} ---")
for k in range(1, 7):
u = A @ u
print(f" k={k} u={u} ||u-u*||={np.abs(u - u_ss).max():.3e}")
# ---------- 5. 用 |lambda_2| 预测误差衰减 ----------
u = np.array([1.0, 0.0, 0.0])
err = []
for k in range(12):
u = A @ u
err.append(np.abs(u - u_ss).max())
print("误差序列:", np.round(err, 6))
print("相邻误差比(应接近 |lambda_2|):",
np.round([err[i + 1] / err[i] for i in range(5)], 4))
# ---------- 6. 周期性反例:不收敛 ----------
P = np.array([[0.0, 1.0], [1.0, 0.0]])
print("周期链特征值:", np.linalg.eigvals(P)) # 1 与 -1
u = np.array([1.0, 0.0])
for k in range(4):
u = P @ u
print(" 周期链迭代:", u)
# ---------- 7. PageRank:阻尼 + 均匀修正,使矩阵全正 ----------
# 转移矩阵 D(第 j 列为从 j 出发到各页面的概率;节点 0 是悬挂节点)
D = np.array([[0.0, 0.0, 1.0 / 3],
[1.0, 0.0, 1.0 / 3],
[0.0, 1.0, 1.0 / 3]])
d = 0.85
n = 3
M = d * D + (1 - d) / n * np.ones((n, n)) # M = dD + (1-d)/n * 1 1^T
print("M 列和:", M.sum(axis=0), " 最小元素:", M.min()) # 应 > 0
w2 = np.linalg.eigvals(M)
print("M 特征值:", w2, " 模:", np.abs(w2))
u = np.array([1.0, 0, 0])
for _ in range(100):
u = M @ u
print("PageRank(归一化):", np.round(u, 6))
运行结果的要点(与 5.1、5.2 节的手算一致):
- 的列和全为 (这是"按列"的直接体现);顺便注意 的行和也恰好都是 (矩阵恰好是双随机的),但这只是巧合——本篇例题 10.2.B 的矩阵行和就是 ,一般随机矩阵的行和不为 ;
- 特征值为 ,收敛速率 ;
- 稳态 ,且 ;
- 从三个不同初值出发,6 步内都收敛到同一稳态,误差按 衰减(相邻误差比 );
- 周期链 的特征值是 与 ,迭代结果在 与 之间振荡,不收敛;
- PageRank 的 全正、列和为 ,特征值的模都小于等于 且只有一个等于 ,迭代收敛到 。
五、例题
例题 10.2.A: 状态链的完整分析(特征值、稳态、迭代验证)
题目 某系统有三个状态 ,转移规则如下(每一步):
- 从状态 1:以 留在 1,以 到 2,以 到 3;
- 从状态 2:以 到 1,以 留在 2,以 到 3;
- 从状态 3:以 到 1,以 到 2,以 留在 3。
(注意状态 2 与状态 3 的转出比例完全相同,这是本题的一个特点。)求:(1) 转移矩阵 ;(2) 全部特征值;(3) 稳态分布 ;(4) 从 出发迭代几步观察收敛。
解
第一步:写出 。 第 列是"从状态 出发的去向",所以
检查:每列之和 ✓, ✓,第三列与第二列相同(因为状态 2、3 的转出比例一样)也 ✓。非负 ✓。是随机矩阵。
第二步:求特征值。 解 :
关键观察:第 2 列与第 3 列完全相同(都是 ),但它们在 里减去的 位置不同(分别在第 2、3 个分量上),所以不能直接说行列式为 。更省力的办法是用列和的等式化简。
先验证 是特征值:定理 10.3.1 保证 是特征值,且 :
用迹与行列式求其余特征值。 记特征值为 。由迹:
再算一个不变量(用 5-3-克莱姆法则与体积 那一章反复使用的"行列式=特征值之积"):三个特征值之积 。注意 的第 2、3 行分别为 与 ,它们不成比例;但第 2、3 列相同,所以 的列秩至多 ,即 (两个相同列 ⟹ 行列式为零,见 5-1-行列式的性质)。于是
结合 ,得 。所以特征值是
逐项验证(用 的秩): 的第 2、3 列相同,故 ;而第 1 列与第 2 列不成比例,故 ,于是 ,即 的几何重数为 ✓(与上面算出的"一个零特征值"一致)。
同时这也说明 是单重特征值(三个特征值 互不相同),所以 可对角化,且 ,稳态唯一(定理 10.3.5 的条件全部满足:除 外的模为 与 ,都严格小于 )。
第三步:求稳态 。 解 (这一步就是求奇异矩阵的零空间,与 2-4-矩阵运算与逆矩阵 里"判断可逆性、求零空间"的手法一致):
把第 2、3 行分别乘 与 化成整数(先乘 再用整数运算更清楚),这里直接做行化简。记三个方程为
式 (1) 两边除以 :,即
式 (2) 两边除以 :,即
式 (3) 两边除以 :。验证它与前两式的相容性:把 (1') 的 代入 (2'):
代回 (1'):。所以 ——三个分量相等。
用式 (3) 复核: ✓(自动成立,说明式 (3) 是前两式的组合,与" 只有一个"相符)。
规范化(各分量之和为 ):,于是
验证: 的分量分别是 ,, ✓,即 。
顺带求出另外两个特征向量(用于第 4 步的收敛性分析):
:解 :
由第 1 式:。由第 2 式:。用 代入:
于是 。取 ,得
注意 有正有负——这很正常:只有 对应的特征向量才能取成全正的概率分布,其余特征向量必然有负分量(因为它们的 次幂要衰减到零,若全正且和为正常数就没法衰减)。
:解 。由第 1 式 ……直接看 :第 2、3 列相同,所以 在零空间里(它让第 2、3 列的贡献相消):
故 。
第四步:从 迭代。 把 按特征向量展开。设
三个方程:
(三个方程分别来自 的第 1、2、3 个分量。)
由第 1 式 。由第 2 式减第 3 式:,即 。代入第 3 式:
与 联立:。于是
注意 :这说明用特征向量展开时系数可以为负——因为 是非负的,但特征向量的组合可以有负系数。而极限 要是概率分布,必须 ,这看起来矛盾。问题出在 的规范化:我取的 已归一化为概率分布(分量和 ),而展开式的系数就要相应调整。让我用未归一化的稳态 重新展开:
第 2 式减第 3 式:。代入第 3 式:。与第 1 式 联立:。于是
现在 ✓,极限是 ✓,与稳态一致(这正好符合" 是概率分布 ⟹ 稳态方向系数 稳态规范化的比例")。
迭代公式:
( 时 ,所以 的成分从第一步起就消失了——这与",一阶收敛"完全对应。)
逐项计算前几步(用 直接乘,最不容易出错):
收敛情况一目了然:、、、,正在朝 收敛。
用误差公式验证速率:误差 为
每次缩小 倍,与 完全吻合 ✓( 衰减)。用公式核对 :
例题完成。
本题的三个可复用技巧
1. 不必展开特征多项式:用""与""(配合"两列相同 ⟹ ")就能定出剩余特征值;
2. 收敛速度直接由 读出,不需要真的迭代很多步;
3. 特征向量展开时用未归一化的稳态(如 ),系数才有"概率质量"的直接含义。
例题 10.2.B:市场份额(两步转移 + 稳态解读)
题目 某市场有三个品牌 ,每季度用户流动情况如下: 的用户中 留下、 转到 、 转到 ; 的用户中 留下、 转到 、 转到 ; 的用户中 留下、 转到 、 转到 。求长期市场份额,并算出两年后( 个季度)与稳态的差距。
解
第一步:写转移矩阵(列 = 当前品牌,行 = 下季度品牌):
列和检查: ✓; ✓; ✓。是随机矩阵,而且全正(所有元素 )⟹ 由推论 10.3.3,稳态唯一且幂迭代必收敛。
第二步:解稳态。 :
由第 2 式:,即
由第 3 式:,即 ,也就是
把 (a) 代入 (b):
代回 (a):。
用第 1 式检验: ✓。
规范化:,于是
长期市场份额:品牌 约 、 约 、 约 。
第三步:估算收敛速度。 特征值中的一个必为 ;用 得 。再用行列式定出乘积:
按第 1 行展开:
于是 ,与 联立:解 ,
所以特征值是 、、(三个互不相同实数, 可对角化,稳态唯一)。numpy.linalg.eig 给出完全一致的结果(可以用 4.3 节代码验证)。
,所以误差每季度乘约 。 个季度后误差约为 倍——已经很小,但还不能说"完全收敛"。
第四步:算出两年后的分布。 取初始份额 (当前市场),计算 。手算 太繁,用迭代(每步只做一次矩阵乘向量):
继续迭代(每一步与稳态 的距离约为上一步的 倍):
两年( 个季度)后的市场份额约为 、、,与稳态 的差距只有约 个百分点 ✓(误差序列 ,相邻之比稳定在 附近,与 完全吻合)。
有趣的一点: 的份额几乎从第一季度的 起就不再变化,因为稳态的第三个分量恰好就是 ,而 的第三个分量也恰好是 ——这说明当某个分量一开始就落在稳态值上时,它会一直保持不变(因为 的这一行对前两个分量的系数之和恰好产生补偿)。但这绝不意味着整个分布已经收敛:误差序列到第 8 步仍有 ,而" 不动"只是"这个方向上恰好没有误差"而已。
例题完成。
例题 10.2.C:PageRank 的完整数值演算( 个网页,国内教材补充)
题目
某小型网站的 个网页 之间的超链接如下( 表示"网页 有一条链接指向网页 "):
( 有一个指向自己的自环。)取阻尼因子 ,求 PageRank 向量。要求:
(1) 写出转移矩阵 与阻尼矩阵 ;
(2) 从均匀初值做幂迭代,写出前 步;
(3) 与" 的特征向量"解对照,并给出 的全部特征值。
解
第 1 步:写出出链数与转移矩阵 。
出链数:(指向 ),(指向 ),(指向 ),(指向 ),(指向 )。
按本篇约定( 当 有链接指向 ), 的第 列是"从 出发的去向":
列和检查: ✓——每个网页都有出链,本例没有悬挂节点。
第 2 步:写出阻尼矩阵 。
,,于是 :
逐列计算():
抽查第 3 列(来自 ):它对 自己贡献 、对 贡献 、对每个网页另有均匀项 。所以第 3 列是
全矩阵检查:列和全为 ✓;最小元素 ✓—— 是正随机矩阵,于是由推论 10.3.3,稳态唯一、全正、幂迭代必收敛。
第 3 步:幂迭代(初值取均匀分布 )。
第 1 步(,此时 的每个分量就是对应行的行和乘以 ……更直接的办法是按列加权求和):
(上面第 1 个分量 的来历:网页 的入链贡献为 ,只剩均匀项 。)
第 2 步:
逐个算出:
于是
继续迭代(用 直接乘,逐项算,不跳步):
观察:
- 第 个分量从第 步起就锁定在 ——因为 没有任何入链,它只能拿到"随机跳转"的底分 ;
- 第 个分量从第 步起锁定在 ——因为 的唯一入链来自 ,而 的分数已恒定,于是 ;
- 第 个分量仍在来回摆动( 先升后降、 先降后升),因为 三个网页构成了一个含二环的子结构。
继续迭代到收敛(幂迭代的极限):
第 4 步:与特征向量解对照。
稳态满足 ,即 。用 numpy 求 的特征值:
逐条解读:
- 单重 ⟹ 稳态唯一();
- 其余特征值的模分别为 ,全部严格小于 ⟹ 幂迭代必收敛(定理 10.3.5);
- 收敛速率 恰好等于 !这不是巧合:网页 与 互相链接构成一个二环(2-cycle), 限制在 上的块是 ,其特征值为 ;再乘阻尼 就得 。所以这个例子的收敛速率达到了 PageRank 的理论最坏值 。
数值验证误差衰减:从均匀初值出发,误差 相邻之比在若干步后稳定在 :
奇数步与偶数步交替出现 ——这正是" 这个负特征值"留下的指纹(负特征值让误差在两步之间换号,平均每两步衰减 )。
第 5 步:用闭式公式复核。
由于 是 的特征向量(对应 ),稳态有闭式
为什么:设 ,即 。因为 (概率分布),右端的 ,于是
一定可逆吗?一定: 的特征值 ,所以 的特征值 , 不是 的特征值,故 可逆 ✓。
numpy 算出的结果是
与幂迭代的极限完全一致(两者之差的最大绝对值 ,纯粹是浮点误差)。
第 6 步:读懂排序结果。
- 排第一:它有两条入链(来自 与 );
- 紧随其后:它有一条"高质量"入链(来自 ,而 本身分高);
- 排第三:它有入链(来自 与自环),但 本身分数低,"被低分页面链接"拿不到多少分;
- 、 垫底: 零入链,只能拿底分; 的唯一入链来自垫底的 ,于是 。
本题体现的三条 PageRank 机制
1. 底分机制: 是每个页面的"保底分",零入链的页面也拿得到(这正是阻尼项的作用:让排名不会因为图不连通而崩掉);
2. 链接传递机制:一个页面把 的权重按出链数均分给邻居,所以"入链多"和"入链质量高"都重要;
3. 收敛速率由 决定,而 。当图里存在长的或奇偶交替的环时, 会逼近 ,收敛变慢——这就是为什么真实 PageRank 需要几十次迭代而不是几次。
例题 10.2.D:稳态与初值无关的完整证明(含数值验证)
题目
设 是 随机矩阵,,。证明:对任意初始概率分布 ,幂迭代 都收敛到同一个极限,且该极限与 无关。
证明
第 1 步: 是正随机矩阵。
- 非负且全正: 的每个元素都 ;
- 列和为 :由 ,
第 2 步: 的特征值结构: 单重,其余模 。
(a) 是特征值(由定理 10.3.1),且其左特征向量是 。
(b) 其余特征值满足 。 设 ,,且 。
先算出 :两边左乘 ,
由 得 。代回 :
所以 ,即 是 的特征值。而随机矩阵的谱半径不超过 (定理 10.3.4 第 1 条),故
(这一步的实质):阻尼项对"非稳态成分"是"隐形的"——只要 ,那项 就完全消失,于是 只是 的特征值。换句话说: 这一项把整个谱"压"到 倍以内(除 之外),同时把 变成单重。
(c) 是单重(代数重数为 )。
先看几何重数。设 ,则与上面同样的推导给出 或 (现在 ,不再能推出 )。改用左特征向量:设 。两边右乘 ,用 的分量:
即 (注意: 的每行和一般不为 ,但 ;不过我们其实不需要这个等式,改用更干净的论证):
更简单的论证: 是全正随机矩阵,直接引用 Perron–Frobenius 定理(推论 10.3.3)即得: 是单重特征值,且其余 。这正是阻尼因子在 PageRank 中不可替代的作用(见 6.4 节第二步)。
第 3 步:幂迭代的极限与初值无关。
由 可对角化( 单重、其余特征值互不相同或不影响对角化——严谨地说, 全正故由 Perron–Frobenius 其 的代数重数为 ,且其余特征值模严格小于 , 的 Jordan 形中对应 的块在幂次下仍然趋于零),把 按特征向量展开:
于是
因为 使每一项 。
第 4 步:系数 由"概率分布"唯一确定,与 的具体形状无关。
取 是任意概率分布(),并取稳态规范化 。在展开式两边左乘 :
由第 2(b) 步,对一切 有 (因为 ),故
(若稳态未规范化,则 ,仍只依赖稳态本身的规范化方式,与 无关。)因此
数值验证(用例题 10.2.C 的 ,分别从四个完全不同的初值出发):
import numpy as np
M = np.array([
[0.03, 0.03, 0.03, 0.03, 0.03],
[0.88, 0.03, 0.03, 0.03, 0.03],
[0.03, 0.88, 0.455, 0.03, 0.03],
[0.03, 0.03, 0.455, 0.03, 0.88],
[0.03, 0.03, 0.03, 0.88, 0.03],
])
# 用闭式公式作为“真值”
d, n = 0.85, 5
P = np.array([
[0, 0, 0, 0, 0],
[1, 0, 0, 0, 0],
[0, 1, 0.5, 0, 0],
[0, 0, 0.5, 0, 1],
[0, 0, 0, 1, 0]], dtype=float)
u_true = (1 - d) / n * np.linalg.solve(np.eye(n) - d * P, np.ones(n))
print("闭式稳态:", np.round(u_true, 8))
for tag, u0 in [("均匀 (1/5,...)", np.ones(5) / 5),
("全在 p1", np.array([1.0, 0, 0, 0, 0])),
("全在 p5", np.array([0.0, 0, 0, 0, 1.0])),
("(0.4,0.3,0.2,0.05,0.05)", np.array([0.4, 0.3, 0.2, 0.05, 0.05]))]:
u = u0.copy()
for _ in range(200):
u = M @ u
print("%-26s -> %s 与真值之差 %.2e" % (tag, np.round(u, 8), np.abs(u - u_true).max()))
输出:
M 是否等于 0.85P + 0.03*11^T : True
闭式稳态: [0.03 0.0555 0.13421739 0.40555817 0.37472444]
uniform -> [0.03 0.0555 0.13421739 0.40555817 0.37472444] diff 1.94e-15
all p1 -> [0.03 0.0555 0.13421739 0.40555817 0.37472444] diff 2.83e-15
all p5 -> [0.03 0.0555 0.13421739 0.40555817 0.37472444] diff 5.61e-15
mixed -> [0.03 0.0555 0.13421739 0.40555817 0.37472444] diff 2.11e-15
四个初值收敛到完全相同的分布(差异都在 量级,纯粹是浮点误差)——这就是"稳态与初值无关"的数值证明。
这一步为什么必须靠" 全正"
证明的第 2(c) 步( 单重)与第 4 步( 唯一)都依赖" 全正"。如果没有阻尼项(即直接对 做幂迭代):
- 图可能不连通 ⟹ 多重 ⟹ 不同初值收敛到不同的稳态(例题 10.2.E);
- 图可能是周期的 ⟹ 存在 而 ⟹ 根本不收敛(例题 10.2.F)。
一句话:阻尼项 一次性买到了"唯一性 + 与初值无关 + 收敛"三件事。
例题 10.2.E(反例一):含吸收态的链——稳态存在但不唯一,极限依赖初值
题目
考虑赌徒破产模型:状态 分别表示赌徒手中的资金为 个单位,资金 与 是吸收态(到游戏结束都不再变化)。转移规则:资金 或 停留在原地;资金 或 时,以 的概率增加 、以 的概率减少 。求:(1) 转移矩阵;(2) 特征值;(3) 从不同初值出发的幂迭代极限。
解
第 1 步:写出转移矩阵。
(矩阵元素逐项读出的过程,与 5-1-行列式的性质 里"按行按列读矩阵"的训练同源;下面还要用行列式判断"两列相同"这类结构。)
列和检查:第 1 列 ✓;第 2 列 ✓;第 3 列 ✓;第 4 列 ✓。是随机矩阵,但不是正矩阵(有零元素)。
第 2 步:特征值。
是二重特征值,重数恰好等于吸收态的个数(状态 与状态 )。由第 1.6 节的一般结论,此时稳态不唯一: 是二维的,里面有两个线性无关的稳态——正是"最终停在状态 "与"最终停在状态 "这两个分布
任何凸组合 也都是稳态——稳态构成一个凸集(这条结论在易错点第 3 条里提过)。
第 3 步:从不同初值迭代,极限不同。
取初值 (赌徒已有 个单位):
用 numpy 迭代 步:
取初值 (赌徒已有 个单位):
两个极限显然不同! 由 可以看出原因:
中间两个状态的列已经衰减到 量级(特征值 与 的 次方),但它们衰减成的比例由初值决定:
- 从状态 (资金 )出发,最终落在吸收态 (破产)的概率是 、落在状态 的概率是 ;
- 从状态 (资金 )出发,落在吸收态 的概率只有 、落在状态 的概率是 。
这两个概率可以用一步分析法验证(设 为"资金 时最终破产的概率",)。更标准的做法是解 ( 是瞬态之间的转移块),其中要用到 求逆公式——见 2-4-矩阵运算与逆矩阵:
结果完全吻合。这两个概率正是经典"赌徒破产"问题的结论(资金少的一方破产概率大),但它们的值完全取决于初值——同一个链,两个初值给出两个不同的极限。
这个反例说明什么
"随机矩阵一定有稳态"是真的(定理 10.3.1),但"稳态唯一"和"极限与初值无关"是额外的条件:
本例中 是可约的(状态 与 都是封闭集合,进去就出不来),所以 二重,稳态一整个凸集,幂迭代的极限完全由初值决定。
这也解释了 1.6 节提到的第二个事实:可约链的长期行为取决于初始分布——在人口迁移模型里就是"两个互不往来的城市群,各自的人口最终按自己的初始比例稳定下来"。
例题 10.2.F(反例二):周期链——稳态存在但幂迭代永不收敛
题目
考虑三个状态轮转的链(状态 ,概率全为 ):
(1) 求全部特征值;(2) 说明为什么 不收敛;(3) 求它的稳态分布;(4) 验证"时间平均"收敛到稳态。
解
第 1 步:特征值。
(按第 1 行展开:。)故
三个特征值的模都等于 (它们是 次单位根):
第 2 步:为什么幂迭代不收敛。
从 出发:
它在一个 -循环里永远轮转,不收敛。 从特征值看:非稳态成分带着 与 ,而 ,永不衰减——违反定理 10.3.5 的条件"除 外 "。
另一个等价的说法:
(走 步必然回到原点),所以"第 步在哪个状态"完全由 除以 的余数决定,初值信息永远不被忘记。这正是定义 10.3.3 所说的周期链(周期为 )。
第 3 步:稳态仍然存在(这是关键)。
解 :
所以"稳态存在"与"幂迭代收敛"是两件不同的事:
- 稳态存在 ⟸ 是特征值(随机矩阵必然如此);
- 幂迭代收敛 ⟸ 除 外所有 (额外条件,周期链不满足)。
第 4 步:时间平均(Cesàro 求和)收敛到稳态。
虽然 自己不收敛,但它的平均收敛:
为什么:定义 ,实际上对周期链可以取 周期 :
秩为 的矩阵,每一列都是稳态 ⟹ 对任何初值 ,,三步平均就精确等于稳态。
numpy 验证:从 出发迭代 步取平均,结果为 ✓。
周期链与 PageRank 的关系
PageRank 引入阻尼因子 ,本质上就是把所有 ()的特征值压到 (例题 10.2.D 第 2(b) 步的证明)。
所以阻尼项同时解决了两类病态:
- 悬挂节点(某一列为全零, 不再是随机矩阵)——阻尼项让每列至少还有 ;
- 周期性(存在 而 )——阻尼项把所有这类特征值乘上 ,使它们严格小于 。
一句话: 是全正的,所以 Perron–Frobenius 可以"一票通过"——唯一稳态、全正、幂迭代必收敛、极限与初值无关。
六、应用
6.1 人口迁移(population migration)
把城市编号 , 是第 年城市 的人口占比, 是"第 城人口每年迁往 城的比例",则 。稳态 就是长期人口分布:
- 若 全正(每对城市之间都有人口流动),则长期分布唯一、与初始分布无关(推论 10.3.3);
- 若存在两个互不往来的城市群,则 可约,长期分布取决于初始分布(3.5 节);
- 越接近 ,人口结构"混合"得越快。
6.2 市场份额与品牌转换(market share)
就是例题 10.2.B。工程实践中的三点经验:
- 稳态给出"竞争终局":如果当前的转换率长期不变,那么无论现在谁领先,最终份额都由 唯一决定;
- 敏感性:稳态对 的元素是否敏感,取决 —— 接近 时,转换率的微小改变会显著移动稳态(这时系统"记忆"很久);
- 要改变终局,就得改变转移率:稳态只是 的函数,短期的促销活动(改变 )不会改变长期份额。
6.3 排队模型与系统可靠性(queueing / reliability)
- 排队模型:把"系统中有 个顾客"作为状态,到达率与离开率决定转移概率。稳态分布给出长期平均队长,这是排队论(M/M/1 等)的核心量。
- 可靠性:把"设备处于健康 / 轻微故障 / 严重故障"作为状态,稳态分布给出长期可用率(availability)——这正是维修策略优化的基础。
- Google 的 PageRank 与马尔可夫链蒙特卡洛(MCMC):后者用精心设计的转移矩阵使目标分布成为稳态,从而通过迭代采样。
6.4 PageRank 的核心思想
问题:如何给网页排序?PageRank 的想法是——"重要"的网页是被重要的网页链接的网页。把它写成线性代数:
第一步:把网页链接建成 Markov 链。 网页是节点,超链接是有向边。设网页 有 条出链,则从 出发沿每条出链走的概率是 。定义转移矩阵 (, 是网页总数):
逐条翻译:若网页 有一条链接指向网页 ,则 ( 是 的出链数);否则 。
的每列和为 (只要 )。于是 是随机矩阵,"随机冲浪者"的分布 ,稳态 就是网页排名。
第二步:为什么需要阻尼因子 ? 原始的超链接图有两个病态:
- 悬挂节点(dangling node):有些网页没有出链,则 , 的第 列全为 —— 不再是随机矩阵,概率质量会"凭空消失";
- 周期性:如果网页两两成对互相链接,冲浪者会永远来回跳(就像 3.4 节的 ),幂迭代不收敛。
修补办法:假设冲浪者以概率 (通常 )沿链接继续走,以概率 随机跳到一个任意网页(均匀分布 )。于是
逐项解释:
- :按链接走的概率加权;
- :一个所有元素都等于 的 矩阵(因为 是全 矩阵);
- 是随机矩阵: ✓;
- 是全正矩阵(每个元素 ),所以由推论 10.3.3:稳态唯一、全正、幂迭代必收敛;
- 的谱结构:,可以证明 的特征值是 (对应稳态)以及 ()。所以 ,收敛速率不超过 。
第三步:为什么关心稀疏性(sparsity)? 真实网页图有 个节点、平均出链约 条,所以 中每列只有约 个非零元,非零元占比约 。若用稠密矩阵存储,需要 个浮点数——完全不可能。因此:
- 存储上只存非零元(稀疏矩阵格式,如 CSR),内存需求从 降到与"非零元个数"成正比(记非零元个数为 ,即 );
- 计算上不用矩阵乘法,而是直接用"沿着链接分发排名"的方式做一次幂迭代(每个节点把 分给出链邻居),复杂度与边数成正比,即 ;
- 绝不解特征方程( 的特征分解毫无可能),而是用幂迭代——因为 ,约 次迭代就够用。这就是"收敛速率"这个数值指标的实际威力。
第四步:与图论的接口。 的构造完全依赖链路结构(即图的关联信息),而阻尼后的 全正 ⟹ 转移图强连通且非周期 ⟹ 由 10-1-图与网络 的语言," 的 特征空间是一维的"。PageRank 把图的结构、随机矩阵的稳态、幂迭代的收敛性三件事合成了一行公式。
6.5 PageRank:从"链接矩阵"到"排名向量"的完整算例小结(国内教材补充)
一句话
PageRank = 一个全正随机矩阵的稳态分布。全部算法内容只有三步:写 、加阻尼得 、幂迭代求 的 特征向量。
第一步: 的构造(列随机的来源)。
设网页 有 条出链,则
注意 里用的是"出链数 "(列下标 ),因为 的第 列描述"从 出发的去向"。若 是悬挂节点(),则该列全零。
第二步:阻尼矩阵。
第三步:幂迭代。
停止准则:(工程中取 量级)。所需步数由 估计:
(这与 4.2 节的公式 完全一致。)
三个"必须交代清楚"的工程细节
1. 悬挂节点的两种处理。 严格来说悬挂节点让 不再是随机矩阵(该列全零,概率质量会"漏掉")。两种常见补法:
- 补均匀列:把该列换成 (等价于"从这个页面出发的冲浪者随机跳到任意页面");
- 不补,靠阻尼项兜底:由于 中 ,即使 该列为零, 该列仍然全为 ,列和依然为 ——注意!这样 的列和就不是 了。
所以工程实现里必须先把悬挂列补成均匀列,再加阻尼,否则 不是随机矩阵, 也不一定再是特征值。这是 PageRank 实现中最容易踩的坑。
数值上看得很清楚(,;第 个网页有 条出链、第 个网页没有出链):
```python
import numpy as np
n, d = 5, 0.85
P = np.zeros((n, n))
P[:4, 0] = 1 / 4 # 第 1 页的 4 条出链,列和为 1
P[:4, 1] = 1 / 4 # 第 2 页同样有 4 条出链
P[:, 2] = 0.0 # 第 3 页是悬挂节点:该列全零
M_bad = d P + (1 - d) / n np.ones((n, n))
print("修补前列和:", M_bad.sum(axis=0)) # 第 3 列只有 0.15
P[:, 2] = 1 / n # 修补:把悬挂列补成均匀列
M_ok = d P + (1 - d) / n np.ones((n, n))
print("修补后列和:", M_ok.sum(axis=0)) # 第 3 列恢复为 1
```
输出:
```
修补前列和: [1. 1. 0.15 0.15 0.15]
修补后列和: [1. 1. 1. 0.15 0.15]
```
未修补时悬挂节点的列和只有 (),概率质量凭空漏掉;把该列补成均匀列后恢复为 ✓。(第 列在这个例子里仍是零列,所以列和是 ;实际数据里每个网页都会有出链。)
结论:" 是随机矩阵"这个性质不可能只靠阻尼项得到,必须先把 修成随机矩阵。
2. 稀疏性决定了"怎么算"。 真实网页图 、平均出链约 ,所以每列只有约 个非零元。实现上绝不构造 的稠密矩阵,而是沿链接分发排名:每个页面把 分给自己的出链邻居,再叠加 的底分。一次迭代的代价与边数成正比,即 。
3. 归一化是必须的。 浮点累积误差会让 缓慢偏离 。每若干步重新规范化 ,或者用 4.1 节方法三的增广方程组。
PageRank 与 Markov 链的对照表(把本篇的概念一次性对齐):
| Markov 链的语言 | PageRank 的语言 | 数学对象 |
|---|---|---|
| 状态 | 网页 | 指标 |
| 一步转移概率 | 沿着一条超链接跳转的概率 | |
| 转移矩阵(列随机) | 超链接矩阵 | , |
| 加入"随机跳转" | 阻尼(damping / teleport) | |
| 稳态分布 | PageRank 向量 | , |
| 收敛速率 | 迭代次数 | |
| 不可约 + 非周期 | 阻尼后的图强连通且非周期 | 全正 |
| 与初值无关 | 不依赖初始排名 | (例题 10.2.D) |
与 10-1-图与网络 的接口: 完全由图的结构(有向图的关联信息)决定; 全正意味着"转移图强连通且非周期",用图论的话说就是" 的特征空间是一维"。PageRank 把图结构、随机矩阵的稳态、幂迭代的收敛性三件事合成了一行公式。
6.6 各类随机矩阵的收敛性对照
稳态是否存在、是否唯一、幂迭代是否收敛,取决于矩阵的结构。对照如下:
| 矩阵类型 | 特征值结构 | 稳态是否唯一 | 幂迭代是否收敛 | 典型例子 |
|---|---|---|---|---|
| 一般随机矩阵(列和为 、元素非负) | 必是特征值,其余 | 不一定( 可能多重) | 不一定 | 含两个吸收态的链 |
| 正随机矩阵(所有元素 ) | 单重,其余 | 唯一,且稳态向量全正 | 必收敛,速率由 决定 | 阻尼后的 PageRank 矩阵 |
| 本原随机矩阵(不可约且非周期) | 同上 | 唯一 | 必收敛 | 强连通非周期图 |
| 周期链(可约或周期) | 存在 且 | 不唯一 | 不收敛(振荡) | |
| 含吸收态的链 | 重数 = 吸收态个数 | 依赖初值 | 收敛到某个吸收态 | 赌徒破产模型 |
表格里最容易忽略的一列是"幂迭代是否收敛"
稳态存在 ≠ 幂迭代收敛。周期链 每列和为 ,也有稳态(任何 都是),
但迭代会在两个状态之间来回振荡,永远不收敛到某一个。
判据是"除 外其余特征值的模是否都严格小于 "——这正是 Perron–Frobenius 定理对正矩阵的结论。
七、易错点
本篇八个高频错误
1. 把行和与列和搞反:随机矩阵的定义是每列和为 (因为 把分布写在右边)。若把分布写成行向量 ,才要求每行和为 。先看 在哪一边,再定"行还是列"。 检查方法:算
A.sum(axis=0),应当全为 。2. 以为"任何随机矩阵都收敛":随机矩阵只保证 是特征值(稳态存在),不保证幂迭代收敛。反例: 的特征值是 ,迭代在两个分布间永远振荡。收敛的充要条件是除 外 。
3. 忘记"稳态与初值无关"有前提:只有当 是单重特征值(转移图强连通)且其余 时,极限才与 无关。若是可约链(如 ,或两个互不相通的封闭集合),不同初值会收敛到不同的稳态。可约链的稳态构成一个凸集(所有稳态分布的凸组合仍是稳态)。
4. 把 当成"稳态是 ": 说明 是 的特征向量(左特征向量),它保证 是特征值;稳态是 的右特征向量 (),一般 。若 不对称, 是常态。
5. 浮点误差让稳态"略微偏离": 一定奇异,直接
np.linalg.solve(A - I, 0)会因矩阵奇异而报错或给出无意义的巨大数值;用幂迭代时,稳态分量的和会缓慢偏离 (每一步乘以列和为 的矩阵理论上保持和不变,但浮点累积误差会让它漂移)。两个对策:每若干步重新规范化 ;或改用增广方程组(本篇 4.1 方法三)。6. 用"行和"去检查随机矩阵的性质: 是列和条件; 是行和条件。只有列和条件才对 有意义。 另外要注意,行和有可能碰巧也全为 (此时 叫双随机矩阵,本篇例题 10.2.A 的矩阵就是),但这是巧合而非定义要求:例题 10.2.B 的矩阵行和分别是 。判断随机矩阵永远只看列和。
7. 以为稳态一定是"各分量相等": 只在双随机矩阵(doubly stochastic,行列和都为 )且不可约时才是稳态。一般随机矩阵的稳态由转移结构决定,各分量一般不相等(例题 10.2.B 的 )。
8. PageRank 里把 误当成 : 中, 是 的全 矩阵,不是向量 。写成 形状就不对;写成 更错(那会破坏每列和为 )。
八、练习题
练习 10.2.1(基础)
判断下列矩阵哪些是随机矩阵(并说明理由):
对每个随机矩阵,求出稳态分布,并判断从任意初值出发的幂迭代是否收敛。
练习 10.2.2(基础)
设 。求特征值、稳态分布,并给出第 步分布 的显式表达式(用初值 )。要求:写出 的每个分量的闭式,并说明 时的极限。
练习 10.2.3(进阶)
设 是三状态周期链
求全部特征值;说明为什么 不收敛;求出它的稳态分布;并验证"时间平均" 收敛到稳态(对任意初值分布)。
练习 10.2.4(进阶)
设 是随机矩阵,且 还是对称的(即 )。证明:
(1) 是双随机的(行和也为 );
(2) 的特征值都是实数,且 ;
(3) 若进一步设 的所有元素 ,则 是唯一的稳态分布。
(提示:对称矩阵可正交对角化,见 6-4-对称矩阵与正定矩阵。)
练习 10.2.5(思考)
设 是随机矩阵, 是单重特征值,其余 。证明:稳态分布 的每个分量都严格为正当且仅当转移图强连通(任意两个状态互通)。
(提示:若某个 ,考察 的方程与""中哪些项非零;反过来用 Perron–Frobenius 或" 全正"论证。)
更多易错点(PageRank 与收敛性专题)
PageRank 与 Markov 链的七个专属陷阱
1. 忘记修悬挂节点就直接加阻尼。 前面 6.5 节已算过:若某列全零而不修补, 的该列列和只有 , 不再是随机矩阵, 也不再被保证是特征值。顺序永远是:先补悬挂列 → 再乘 → 再加均匀项。
2. 把"随机跳转的概率"记成 而不是 。 冲浪者以概率 跳转,跳到 个页面中的某一个,所以每个页面分到 。写成 (向量)形状就不对,必须是 ( 的全 矩阵)。
3. 误以为 一定远小于 。 例题 10.2.C 里 ,达到了理论最坏值(因为 构成二环)。所以"阻尼因子 意味着迭代很快"这句话是错的—— 只是上界,真实速率取决于图的结构。见到长链或二环就要预期慢收敛。
4. 用" 是特征值"推出"幂迭代必收敛"。 这是本篇最核心的区分:稳态存在是必然的(定理 10.3.1),幂迭代收敛要额外条件(除 外 )。例题 10.2.F 的周期链就是稳态存在但不收敛;例题 10.2.E 的吸收链是稳态存在、收敛、但极限依赖初值。
5. 把"稳态唯一"与"极限与初值无关"混为一谈。 三者是递进关系:
只在" 单重"还不够—— 还必须"其余 "才能保证收敛;两者都满足时极限才唯一。可约链(例题 10.2.E)是" 非单重",周期链(例题 10.2.F)是"其余 ",分别破坏了后两个条件。
6. 认为"时间平均"没有用。 周期链的瞬时分布 不收敛,但 Cesàro 平均 一定收敛到稳态(例题 10.2.F 第 4 步给出了 恰好是列全为稳态的秩 矩阵)。这是 MCMC(马尔可夫链蒙特卡洛)方法的理论基础:不能取最后一个样本,要取平均。
7. 把 的"列和 = 1"写成"行和 = 1"。 本篇(与 Strang 教材一致)约定 ,所以是列和为 。若改用 (行向量写法),才是行和为 。两种写法互为转置,但绝不能混用。 检查方法:
A.sum(axis=0)应全为 。
补充练习(PageRank 与收敛性,配合第八节)
补充练习 10.2.6(基础) 对例题 10.2.C 的 网页图,把阻尼因子从 改成 。
(1) 重新写出 ;
(2) 用闭式公式 求新稳态;
(3) 说明"零入链页面的分数"为什么从 变成 ,并解释 变小对排名的影响(提示: 越小,均匀项越大,排名越"平均")。
补充练习 10.2.7(进阶) 设 是随机矩阵,,。证明:若 是 的特征值且 ,则 是 的特征值(这就是例题 10.2.D 第 2(b) 步)。要求:写清楚"为什么可以左乘 并得到 "这一步。
补充练习 10.2.8(进阶) 考虑三状态链
(1) 验证它是随机矩阵;(2) 求全部特征值(提示:注意有一个特征值是 ,另外两个是复的);
(3) 判断幂迭代是否收敛,若不收敛,说明它属于哪一类病态(周期?可约?);
(4) 若给 加上阻尼(,),求 的特征值并说明为什么此时一定收敛。
补充练习 10.2.9(思考) 设 是随机矩阵 的稳态,。
(1) 证明 也是随机矩阵;
(2) 证明 也是 的稳态;
(3) 举例说明 的稳态可能比 的"更多"(提示:考虑周期链 ,此时 ,)。
九、常见问题 FAQ
Q1:为什么"每列和为 "就一定能推出 是特征值?
因为列和条件等价于 ,转置得 :这说明 是 的特征向量(特征值 )。而 与 有相同的特征多项式 ,所以 也是 的特征值。这是本篇最短也最重要的一条推理链,它同时给出了"存在性"(稳态一定有)和"它长什么样"( 里的向量)。
Q2:稳态一定能使幂迭代收敛吗?
不一定。 "稳态存在"只需要 是特征值(随机矩阵必然如此);而"幂迭代收敛"还需要其余特征值的模严格小于 。周期链是最典型的反例( 的模也是 ),此时 永远振荡,虽然"时间平均"会趋向稳态(Cesàro 收敛)。PageRank 引入 的阻尼因子,本质上就是把所有 ()的特征值压到 。
Q3: 与"收敛速度"的关系怎么用?
误差 大致按 衰减。所以:
- 想达到 精度,需要 步;
- 时约 步;(PageRank)时约 步; 时约 步。
这是"数值线性代数"里"迭代法收敛率"的一个最直观的实例(可与 11-3-迭代方法与预条件 的 Jacobi/Gauss–Seidel 收敛率对照,那里的收敛率由迭代矩阵的谱半径决定,道理完全相同)。
Q4:PageRank 为什么不会被"链接农场"(link farm)轻易操纵?
因为阻尼矩阵 是全正的,稳态是 的唯一 特征向量,而且它由整个图决定:一个人为制造的、只与自己人互链的页面群,其内部链接只能在那一个小集合里循环,而 那一项让每个页面都能从全网获得均匀的"底分"。再加上 使迭代稳定,PageRank 对局部操纵有天然的抵抗力——这些性质全部是"矩阵全正 + 特征值分布"的直接推论,而不是工程技巧。
本篇小结
一、核心结论(十句话)
- 随机矩阵:元素非负、每列和为 (因为 ,分布写在 的右边)。等价地 。
- 一定是特征值:由 转置得 ,而 与 的特征多项式相同。这保证稳态存在。
- 不是说"稳态是 ":它给出左特征向量;稳态是右特征向量 ()。
- 谱半径 :用"取模最大分量"论证 ,且 必在其中。
- 幂迭代收敛的判据:除 外所有 。收敛速率 (按模第二大者),误差按 衰减。
- 稳态存在 幂迭代收敛:周期链(例题 10.2.F)稳态存在但迭代永远振荡;此时 Cesàro 平均(时间平均)仍收敛到稳态。
- 稳态唯一 + 极限与初值无关 需要 单重且其余 ; 全正(Perron–Frobenius)一次性保证这两条,还额外保证稳态全正。
- PageRank 的核心公式:(), 全正 ⟹ 唯一稳态 + 幂迭代必收敛 + 与初值无关。
- 的谱结构:,其余 ,故 ;阻尼项对"非稳态成分"完全隐形(因为那些特征向量与 正交)。
- 工程三要素:先修补悬挂节点、只存非零元(稀疏)、每若干步重新规范化。绝不解特征方程,用幂迭代。
二、易混概念对照表
| 容易混淆的一对 | 它们分别是什么 | 一句话区分 |
|---|---|---|
| 稳态存在 与 幂迭代收敛 | 是特征值(必然)vs 其余 (额外条件) | 前者是必然,后者是条件;周期链是反例 |
| 与 | 左特征向量 vs 右特征向量(稳态) | 前者保证稳态存在,后者给出稳态是什么 |
| 列和 与 行和 | (本篇)vs (行向量写法) | 先看 在 的哪一边,再定行或列 |
| 双随机矩阵 与 一般随机矩阵 | 行列和都为 vs 只有列和为 | 只有双随机且不可约时稳态才是 |
| 与 | 实际收敛速率 vs 收敛速率的上界 | 例题 10.2.C 中 ,上界取到等号 |
| 周期性 与 可约性 | 存在 而 vs 的重数 | 前者不收敛,后者收敛但极限依赖初值 |
| 瞬时分布 与 时间平均 | (周期链时不收敛)vs (一定收敛) | MCMC 用后者 |
| 阻尼项的两项 | (沿链接走)vs (随机跳转) | 前者保结构,后者保"全正" |
| 悬挂节点 与 周期链 | 某列全零(不是随机矩阵)vs (特征值在单位圆上) | 前者要补列,后者要加阻尼 |
| PageRank 的 与 | 原始超链接矩阵 vs 阻尼后矩阵 | 只有 才保证唯一稳态与收敛 |
| 稳态唯一 与 稳态全正 | 单重 vs 对应特征向量每个分量 | 图强连通时二者等价(练习 10.2.5);全正矩阵同时给出两者 |
三、三句话记住全篇
用一张卡片背下本篇:
- 存在性靠 ;
- 唯一性靠" 单重"(转移图强连通);
- 收敛性靠"其余 ",速率 ;
- PageRank 用全正矩阵 把这三条一次性买到。
相关笔记
- 10-1-图与网络 —— 有向图的关联矩阵、拉普拉斯矩阵与 KCL,本篇是它的"概率版":把每列和为 换成每列和为 ,KCL 就变成"概率质量守恒"
- 6-2-矩阵的对角化 —— 是收敛性定理(10.3.5)的全部技术基础
- 6-1-特征值引论 —— 特征值、特征多项式、迹与行列式的联系(例题 10.2.A 用它免去展开三次多项式)
- 6-4-对称矩阵与正定矩阵 —— 对称随机矩阵(双随机矩阵)的谱性质与练习 10.2.4
- 3-5-四大子空间的维数 —— 就是" 的几何重数",也是稳态空间的维数
- 11-3-迭代方法与预条件 —— 幂迭代与 Jacobi/Gauss–Seidel 的共同语言:谱半径决定收敛速度
- 8-1-线性变换的思想 —— "正实数集配上'加法 = 乘法、数乘 = 乘方'构成一个线性空间"这个怪例(那篇第十节 10.4)说明:把一个乘法型的过程取对数就变成普通的加法型线性过程,这正是本篇处理随机矩阵时"取对数看增长率"技巧的公理依据。
参考来源
- MIT 18.06 Linear Algebra, Lecture 24: Markov matrices; Fourier series:<https://ocw.mit.edu/courses/18-06-linear-algebra-spring-2010/resources/lecture-24-markov-matrices-fourier-series/>
- MIT 18.06 Linear Algebra, Lecture 21: Eigenvalues and eigenvectors:<https://ocw.mit.edu/courses/18-06-linear-algebra-spring-2010/resources/lecture-21-eigenvalues-and-eigenvectors/>
- Gilbert Strang, Introduction to Linear Algebra, 5th ed., Wellesley-Cambridge Press, 2016(第 10.3 节 Markov Matrices, Population, and Economics):<https://math.mit.edu/~gs/linearalgebra/>
- NumPy 官方文档
numpy.linalg.eig(特征值与左/右特征向量的区别):<https://numpy.org/doc/stable/reference/generated/numpy.linalg.eig.html> - NumPy 官方文档
numpy.linalg.matrix_rank(判断 的几何重数):<https://numpy.org/doc/stable/reference/generated/numpy.linalg.matrix_rank.html> - 同济大学数学系《线性代数》第六版,高等教育出版社(第五章「相似矩阵及二次型」为对照章节)