w wyl123ly 的博客
MD

10-2-Markov矩阵与稳态

104 KB 2026.10.11 原文件

10-2-Markov矩阵与稳态

一句话概括

随机矩阵(Markov matrix) 是"元素非负、每列和为 "的方阵。它的第 列是一个概率分布,而 把第 步的概率分布映成第 步的概率分布。由"每列和为 "立刻得到 ,即 一定是特征值;对应的特征向量 满足 ,就是稳态(steady state)。幂迭代 收敛到稳态的充要条件是"除 外其余特征值的模都小于 "——这解释了为什么周期链会不收敛,也是 PageRank 必须引入阻尼因子的原因。

本篇覆盖:随机矩阵的定义与"为什么按列",状态转移的建模,稳态的定义与存在性证明,Perron–Frobenius 定理的完整表述与直观解释,收敛性的充要条件(含周期链反例),一个 状态的完整数值例题(求 、求特征值、求稳态、迭代验证收敛),PageRank 的核心思想(阻尼因子 、悬挂节点、稀疏性),一段可运行的 numpy 代码(构造随机矩阵、幂迭代求稳态、用特征值预测收敛速度),以及人口迁移、市场份额、排队模型等应用。

这一章是"特征值理论 + 应用"最漂亮的一次会面:矩阵的幂、特征值的模、马尔可夫链的长期行为,三件事说的是同一件事。

一、定义

1.1 随机矩阵是"把概率分布映成概率分布"的矩阵

定义 10.3.1(随机矩阵,Markov matrix / stochastic matrix) 设 是 实矩阵。若满足

  1. 非负性: 对一切 ;
  2. 每列和为 : 对每个 成立,

则称 为随机矩阵(也叫马尔可夫矩阵、列随机矩阵)。

第 列就是一个概率分布: 表示"当前处于状态 时,下一步转移到状态 的概率"。写成矩阵:

(意思是:第一列的各分量之和为 ,第二列、第三列……同样如此。)

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 为什么"列和"这个条件如此有力

一个 矩阵有 个自由度,而"每列和为 "只给了 个约束——看似不多,但它一下子钉死了两件事:

  1. 存在: ⟹ 是特征值 ⟹ 稳态存在;
  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 求稳态的三种方法

方法一:解线性方程组(精确解,推荐手算)

稳态满足 ,即 是 中的非零向量。取 的基向量,再按"分量之和为 "规范化。

步骤:

  1. 写出 ;
  2. 对它做行化简,求零空间的一组基;
  3. 把基向量按比例缩放,使其各分量之和为 (若基向量有负分量,说明它不是合法的概率分布——那通常意味着 不满足本篇假设,需要检查)。

方法二:幂迭代(数值解,推荐大规模问题)

,反复迭代直到变化很小。收敛速率由 决定;误差按 衰减。

方法三:解增广方程组(数值上最稳的"直接法")

把 去掉一个冗余方程,换上规范化条件 :

(第一块是 的前 行,最后一行是规范化条件 。)

这是 个方程、 个未知数,且矩阵可逆(前提是 单重),可以直接解。本篇的 numpy 示例就用这一种。

4.2 判断收敛性与估计速度的四步

  1. 算 的全部特征值( 必有一个);
  2. 看除 外是否所有 :是 ⟹ 幂迭代收敛;否(存在 )⟹ 周期链,不收敛;
  3. 若收敛,收敛速率 (按模第二大者);
  4. 需要 精度时,迭代次数约 。

一个常用速算

时,,要 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。工程实践中的三点经验:

  1. 稳态给出"竞争终局":如果当前的转换率长期不变,那么无论现在谁领先,最终份额都由 唯一决定;
  2. 敏感性:稳态对 的元素是否敏感,取决 —— 接近 时,转换率的微小改变会显著移动稳态(这时系统"记忆"很久);
  3. 要改变终局,就得改变转移率:稳态只是 的函数,短期的促销活动(改变 )不会改变长期份额。

6.3 排队模型与系统可靠性(queueing / reliability)

  • 排队模型:把"系统中有 个顾客"作为状态,到达率与离开率决定转移概率。稳态分布给出长期平均队长,这是排队论(M/M/1 等)的核心量。
  • 可靠性:把"设备处于健康 / 轻微故障 / 严重故障"作为状态,稳态分布给出长期可用率(availability)——这正是维修策略优化的基础。
  • Google 的 PageRank 与马尔可夫链蒙特卡洛(MCMC):后者用精心设计的转移矩阵使目标分布成为稳态,从而通过迭代采样。

6.4 PageRank 的核心思想

问题:如何给网页排序?PageRank 的想法是——"重要"的网页是被重要的网页链接的网页。把它写成线性代数:

第一步:把网页链接建成 Markov 链。 网页是节点,超链接是有向边。设网页 有 条出链,则从 出发沿每条出链走的概率是 。定义转移矩阵 (, 是网页总数):

逐条翻译:若网页 有一条链接指向网页 ,则 ( 是 的出链数);否则 。

的每列和为 (只要 )。于是 是随机矩阵,"随机冲浪者"的分布 ,稳态 就是网页排名。

第二步:为什么需要阻尼因子 ? 原始的超链接图有两个病态:

  1. 悬挂节点(dangling node):有些网页没有出链,则 , 的第 列全为 —— 不再是随机矩阵,概率质量会"凭空消失";
  2. 周期性:如果网页两两成对互相链接,冲浪者会永远来回跳(就像 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 对局部操纵有天然的抵抗力——这些性质全部是"矩阵全正 + 特征值分布"的直接推论,而不是工程技巧。


本篇小结

一、核心结论(十句话)

  1. 随机矩阵:元素非负、每列和为 (因为 ,分布写在 的右边)。等价地 。
  2. 一定是特征值:由 转置得 ,而 与 的特征多项式相同。这保证稳态存在。
  3. 不是说"稳态是 ":它给出左特征向量;稳态是右特征向量 ()。
  4. 谱半径 :用"取模最大分量"论证 ,且 必在其中。
  5. 幂迭代收敛的判据:除 外所有 。收敛速率 (按模第二大者),误差按 衰减。
  6. 稳态存在 幂迭代收敛:周期链(例题 10.2.F)稳态存在但迭代永远振荡;此时 Cesàro 平均(时间平均)仍收敛到稳态。
  7. 稳态唯一 + 极限与初值无关 需要 单重且其余 ; 全正(Perron–Frobenius)一次性保证这两条,还额外保证稳态全正。
  8. PageRank 的核心公式:(), 全正 ⟹ 唯一稳态 + 幂迭代必收敛 + 与初值无关。
  9. 的谱结构:,其余 ,故 ;阻尼项对"非稳态成分"完全隐形(因为那些特征向量与 正交)。
  10. 工程三要素:先修补悬挂节点、只存非零元(稀疏)、每若干步重新规范化。绝不解特征方程,用幂迭代。

二、易混概念对照表

容易混淆的一对它们分别是什么一句话区分
稳态存在 与 幂迭代收敛 是特征值(必然)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>
  • 同济大学数学系《线性代数》第六版,高等教育出版社(第五章「相似矩阵及二次型」为对照章节)