图与概率的完美结合
本章将图的邻接矩阵与马尔科夫链的转移矩阵联系起来。 邻接矩阵描述图的连接关系，而转移矩阵描述状态间的转移概率。 通过归一化，邻接矩阵可以转化为转移矩阵。
这种联系不仅优美，而且实用：它让我们可以用矩阵运算来模拟随机过程， 用图论工具来分析概率系统。
✦
20.1
再看邻接矩阵
矩阵的幂 = 路径计数
前面我们学习了邻接矩阵表示图的连接关系。 现在我们发现：邻接矩阵的n次幂An有着深刻的组合意义—— An[i][j]表示从节点i到节点j经过恰好n步的路径数量。
🎯 矩阵乘法的组合意义
A1 = A
• 直达路径（0个中间节点）
• A[i][j] = 1表示i和j直接相连
• 例如：a → f（1条路径）
• A[i][j] = 1表示i和j直接相连
• 例如：a → f（1条路径）
A2
• 途径1个中间节点
• A²[i][j]表示i经过某个k到达j
• 例如：a → b → f, a → c → f（2条路径）
• A²[i][j]表示i经过某个k到达j
• 例如：a → b → f, a → c → f（2条路径）
A3
• 途径2个中间节点
• 路径数量指数增长
• 例如：a → b → a → f等（13条路径）
• 路径数量指数增长
• 例如：a → b → a → f等（13条路径）
A + A² + A³
• 不超过3步的所有路径
• 累加不同长度的路径数
• 累加不同长度的路径数
✦
20.2
转移矩阵：可能性
从连接关系到转移概率
如果我们在邻接矩阵的基础上，假设从每个节点出发到其相邻节点的可能性相同， 就可以得到转移矩阵。方法是：将邻接矩阵的每列（或每行）除以该列（或行）的和， 使其归一化为概率分布。
📐 两种归一化方式
列归一化：T
• T[i][j] = A[i][j] / ΣkA[k][j]
• 每列元素和 = 1
• xi+1 = T · xi
• 状态向量为列向量
行归一化：TT
• TT[i][j] = A[i][j] / ΣkA[i][k]
• 每行元素和 = 1
• xi+1 = xi · TT
• 状态向量为行向量
🔄 状态转移
转移矩阵描述了从当前状态到下一状态的概率。
xi+1 = T · xi
通过矩阵-向量乘法
计算下一时刻的状态分布
计算下一时刻的状态分布
对于无向图，邻接矩阵是对称矩阵； 对于有向图，邻接矩阵通常不对称。
✦
20.3
转移矩阵：有向图
非对称邻接矩阵与转移矩阵
有向图的邻接矩阵通常不对称。 对于有向图，转移矩阵同样可以通过归一化得到。 经典例子包括"鸡兔互变"和航班网络。 通过交互式动画，我们将揭示状态向量如何通过矩阵乘法实现转移。
✦
20.4
马尔科夫链
无记忆性质与稳态收敛
马尔科夫链是具有离散状态的马尔科夫过程。 其核心特征是"无记忆"性质： 系统的下一状态只依赖于当前状态，与如何到达当前状态无关。 满足不可约、非周期、正常返三个条件的马尔科夫链，会收敛到唯一的稳态分布。
🎯 马尔科夫链的三大性质
1. 不可约性 (Irreducible)
定义：从任何状态都可以到达任何其他状态
反例：图中有不连通的分量
保证能探索整个状态空间
2. 非周期性 (Aperiodic)
定义：返回同一状态不需要固定步数
反例：只能在特定步数返回（周期图）
避免陷入固定循环
3. 正常返 (Positive Recurrent)
定义：期望返回时间有限
反例：从某状态出发无法返回（暂态）
保证状态会被反复访问
不可约 + 非周期 + 正常返 → 唯一稳态分布
无论从哪个状态开始，最终都会收敛到相同的概率分布
✦
本章小结
本章将图论、线性代数和概率统计三个领域完美融合。 邻接矩阵不仅描述图的连接关系，通过归一化还可以变成描述状态转移的概率矩阵。 马尔科夫链则是这一框架下最重要的应用。
🎯 核心概念
1
矩阵幂的意义
An[i][j] = 从i到j经过n步的路径数
2
邻接矩阵→转移矩阵
通过归一化（列或行和为1）
3
马尔科夫链
无记忆性质 + 稳态收敛
4
有向图 vs 无向图
对称矩阵 vs 非对称矩阵
💡 关键公式
路径计数
An = A · A · ... · A (n次)
转移矩阵
T[i][j] = A[i][j] / ΣkA[k][j]
状态转移
xi+1 = T · xi
马尔科夫性质
P(Xi+1|Xi) 独立于历史
✨ 三位一体的优雅 ✨
图 ⇄ 矩阵 ⇄ 概率
图论视角
节点、边、路径、连通性
矩阵视角
邻接矩阵、矩阵幂、特征值
概率视角
状态、转移、稳态、收敛