马尔可夫链与转移矩阵：当矩阵编码概率

回顾 Art. 14 算子全景的概念地图：

	状态可观测	状态隐藏
离散状态	马尔可夫链 ← 你在这里	HMM（Art. 16）
连续状态	线性动力系统（Art. 17）	Kalman 滤波（Art. 17）

离散状态、可观测——这是 Part 2 时序算子子线最简单的起点。系统有有限个可数的状态，每一步按固定概率从一个状态跳到另一个，而且我们能直接看到系统处在哪个状态。全部信息都编码在一个矩阵里——转移矩阵 $P$。

为什么从这里开始？因为马尔可夫链是 Part 2 的 “Hello World”：它用最少的设定，展示了 Part 1 工具（特别是特征分解）在算子语境下的核心应用模式——稳态分布就是特征值 1 对应的特征向量，收敛速度由第二大特征值决定。 这个模式将反复出现在后续的 HMM、PageRank、图扩散等场景中。

从直觉出发：天气模型

假设某地的天气只有三种状态：晴天（A）、阴天（B）、雨天（C）。通过统计历史数据，我们发现：

• 今天晴天 → 明天：20% 还是晴天，60% 变阴，20% 下雨
• 今天阴天 → 明天：30% 变晴，30% 还是阴天，40% 下雨
• 今天雨天 → 明天：50% 变晴，10% 变阴，40% 还是雨天

这些数字完全描述了系统的演化规则。明天的天气只取决于今天的天气，而与之前的历史无关——这就是马尔可夫性（Markov property）。

把这些转移概率排成一个矩阵：

$P = \begin{bmatrix} 0.2 & 0.6 & 0.2 \\ 0.3 & 0.3 & 0.4 \\ 0.5 & 0.1 & 0.4 \end{bmatrix}$

其中 $P_{ij}$ 表示从状态 $i$ 转移到状态 $j$ 的概率。这就是转移矩阵（transition matrix），也称为随机矩阵（stochastic matrix）。

下面的状态转移图直观展示了这三个状态之间的所有转移概率——每条边上的数字就是 $P_{ij}$，每个节点的出边概率之和为 1。

现在我们关心的问题是：

1. 长期行为：经过无穷多步转移后，系统处在各状态的概率是什么？
2. 收敛速度：多少步之后，系统”忘记”了初始状态？
3. 数学工具：这些问题和特征分解有什么关系？

转移矩阵的严格定义

定义

设 $\{X_t\}_{t=0,1,2,\ldots}$ 是一个随机过程（random process），取值于有限状态空间 $\mathcal{S} = \{1, 2, \ldots, n\}$。如果对所有 $t \geq 0$ 和所有状态 $i_0, i_1, \ldots, i_{t+1} \in \mathcal{S}$：

$\Pr(X_{t+1} = i_{t+1} \mid X_t = i_t, X_{t-1} = i_{t-1}, \ldots, X_0 = i_0) = \Pr(X_{t+1} = i_{t+1} \mid X_t = i_t)$

则称 $\{X_t\}$ 是一个马尔可夫链（Markov chain）。

逐项理解这个定义：

• 左边：知道全部历史 $X_0, X_1, \ldots, X_t$ 后，$X_{t+1}$ 的条件分布
• 右边：只知道当前状态 $X_t$ 后，$X_{t+1}$ 的条件分布
• 等号的含义：给定当前状态，未来与过去无关——这就是无记忆性（memorylessness）

如果转移概率不随时间 $t$ 变化（即 $\Pr(X_{t+1} = j \mid X_t = i)$ 对所有 $t$ 都相同），则称马尔可夫链是时齐的（time-homogeneous）。本文只讨论时齐马尔可夫链。

转移矩阵 $P$

定义 $n \times n$ 矩阵 $P$，其中：

$P_{ij} = \Pr(X_{t+1} = j \mid X_t = i), \quad i, j \in \{1, 2, \ldots, n\}$

$P$ 是一个（行）随机矩阵（row stochastic matrix），满足两个条件：

1. 非负性：$P_{ij} \geq 0$，对所有 $i, j$
2. 行和为 1：$\sum_{j=1}^{n} P_{ij} = 1$，对所有 $i$

第一个条件是因为概率不能为负。第二个条件是因为从任意状态 $i$ 出发，转移到所有可能状态的概率之和必须为 1——每一行是一个概率分布。

分布的演化：矩阵乘法 = 概率传播

设 $\boldsymbol{\pi}_t \in \mathbb{R}^n$ 是时刻 $t$ 的状态分布（行向量），即 $(\boldsymbol{\pi}_t)_j = \Pr(X_t = j)$。那么一步转移后：

$(\boldsymbol{\pi}_{t+1})_j = \sum_{i=1}^{n} (\boldsymbol{\pi}_t)_i \cdot P_{ij}$

这正是行向量与矩阵的乘法：

$\boldsymbol{\pi}_{t+1} = \boldsymbol{\pi}_t P$

$n$ 步之后：

$\boldsymbol{\pi}_{t+n} = \boldsymbol{\pi}_t P^n$

核心洞察：乘一次 $P$ 就是执行一步转移。矩阵幂 $P^n$ 编码了 $n$ 步转移的全部信息——$(P^n)_{ij}$ 就是从状态 $i$ 出发，经过 $n$ 步到达状态 $j$ 的概率。

这正是 Art. 14 算子全景 中”矩阵本身就是一个过程——乘一次就是执行一步”的具体实例。

稳态分布与特征值 1

稳态分布的定义

如果存在一个分布 $\boldsymbol{\pi}^*$（行向量，非负，分量和为 1）满足：

$\boldsymbol{\pi}^* = \boldsymbol{\pi}^* P$

则称 $\boldsymbol{\pi}^*$ 为 $P$ 的稳态分布（stationary distribution），也称不变分布（invariant distribution）。

直觉上：如果系统的状态分布已经是 $\boldsymbol{\pi}^*$，那么再做一步转移后，分布不变。系统达到了”动态平衡”——每个状态的流入概率恰好等于流出概率。

稳态分布就是特征向量

等式 $\boldsymbol{\pi}^* = \boldsymbol{\pi}^* P$ 可以改写为 $\boldsymbol{\pi}^* P = 1 \cdot \boldsymbol{\pi}^*$。这正是说：

$\boldsymbol{\pi}^*$ 是转移矩阵 $P$ 的左特征向量，对应特征值 $\lambda = 1$。

等价地，转置后：$P^T \boldsymbol{\pi}^{*T} = 1 \cdot \boldsymbol{\pi}^{*T}$，即 $\boldsymbol{\pi}^{*T}$（列向量）是 $P^T$ 的（右）特征向量，对应特征值 1。

这是 Part 1 工具的直接应用——Art. 2 特征分解教我们如何找特征值和特征向量，现在这个工具用来找稳态分布。

为什么特征值 1 一定存在？

命题：任何行随机矩阵 $P$ 都有特征值 $\lambda = 1$。

证明：考虑全 1 列向量 $\mathbf{1} = \begin{bmatrix}1\\1\\\vdots\\1\end{bmatrix}$。因为 $P$ 的每行之和为 1：

$P\mathbf{1} = \begin{bmatrix}\sum_j P_{1j} \\ \sum_j P_{2j} \\ \vdots \\ \sum_j P_{nj}\end{bmatrix} = \begin{bmatrix}1\\1\\\vdots\\1\end{bmatrix} = \mathbf{1}$

所以 $\mathbf{1}$ 是 $P$ 的右特征向量，对应特征值 $\lambda = 1$。$\blacksquare$

注意左特征向量和右特征向量的区别：$\mathbf{1}$ 是 $P$ 的右特征向量（$P\mathbf{1} = \mathbf{1}$），稳态分布 $\boldsymbol{\pi}^*$ 是 $P$ 的左特征向量（$\boldsymbol{\pi}^* P = \boldsymbol{\pi}^*$）。对于一般矩阵，左右特征向量不同，但它们对应的特征值集合相同（因为 $P$ 和 $P^T$ 有相同的特征多项式）。

为什么所有特征值的模不超过 1？

命题：行随机矩阵 $P$ 的所有特征值满足 $|\lambda| \leq 1$。

证明思路：设 $\lambda$ 是 $P$ 的特征值，$\mathbf{x}$ 是对应的（可能是复数的）特征向量。设 $|x_k| = \max_i |x_i|$（模最大的分量）。由 $P\mathbf{x} = \lambda \mathbf{x}$：

$\lambda x_k = \sum_{j=1}^{n} P_{kj} x_j$

取绝对值：

$|\lambda| \cdot |x_k| = \left|\sum_{j=1}^{n} P_{kj} x_j\right| \leq \sum_{j=1}^{n} P_{kj} |x_j| \leq |x_k| \sum_{j=1}^{n} P_{kj} = |x_k|$

因为 $|x_k| > 0$（$\mathbf{x} \neq \mathbf{0}$），两边除以 $|x_k|$ 得到 $|\lambda| \leq 1$。$\blacksquare$

这意味着转移矩阵的特征值全部”锁”在复平面的单位圆内（含边界）。回忆 Art. 14 算子全景 中随机矩阵谱的图示——所有点都在单位圆之内，这就是数学保证。

下图展示了天气模型转移矩阵的三个特征值在复平面上的位置——$\lambda_1 = 1$ 在单位圆边界上，其余两个在半径 $|\lambda_2| = 0.2$ 的小圆内。谱隙 $\gamma = 1 - |\lambda_2| = 0.8$ 非常大，预示着系统会快速收敛到稳态。

Perron-Frobenius 定理

上面我们证明了 $\lambda = 1$ 是一个特征值，且所有特征值的模不超过 1。但这还不够——我们想知道 $\lambda = 1$ 是否是唯一的最大特征值，以及稳态分布是否唯一。这就是 Perron-Frobenius 定理回答的问题。

两个关键条件

在陈述定理之前，需要两个重要的结构性条件：

不可约性（Irreducibility）：马尔可夫链是不可约的，如果从任意状态 $i$ 出发，都能以正概率在有限步内到达任意状态 $j$。即对所有 $i, j$，存在 $m \geq 1$ 使得 $(P^m)_{ij} > 0$。

直觉：图是强连通的——没有”孤岛”或”死胡同”。

非周期性（Aperiodicity）：状态 $i$ 的周期定义为 $d_i = \gcd\{n \geq 1 : (P^n)_{ii} > 0\}$（所有能回到自身的步数的最大公约数）。如果 $d_i = 1$，则状态 $i$ 是非周期的。对于不可约链，所有状态的周期相同；如果这个共同周期为 1，则链是非周期的。

直觉：系统不会陷入”固定节拍”的循环——例如，不会只在偶数步才回到某个状态。

检测非周期性的简单充分条件：如果存在某个状态 $i$ 满足 $P_{ii} > 0$（即有自环），那么 $d_i = 1$，链是非周期的。在上面的天气例子中，$P_{11} = 0.2 > 0$，所以链是非周期的。

定理陈述

Perron-Frobenius 定理（应用于随机矩阵的版本）：设 $P$ 是 $n \times n$ 的行随机矩阵，对应的马尔可夫链是不可约且非周期的。则：

1. $\lambda_1 = 1$ 是 $P$ 的简单特征值（代数重数为 1）
2. 所有其他特征值满足 $|\lambda_i| < 1$（严格小于 1）
3. 存在唯一的稳态分布 $\boldsymbol{\pi}^*$，其所有分量严格为正（$\pi^*_i > 0$）
4. 对任意初始分布 $\boldsymbol{\pi}_0$，$\boldsymbol{\pi}_0 P^n \to \boldsymbol{\pi}^*$（$n \to \infty$）

逐项解读：

• 条件 1-2：$\lambda_1 = 1$ 是严格的主特征值（strictly dominant eigenvalue）。这意味着 $P^n$ 的所有非稳态分量都会衰减到零。
• 条件 3：稳态分布存在且唯一，每个状态都有正概率——没有”永远不被访问”的状态。
• 条件 4：无论从哪里出发，系统最终都会收敛到同一个稳态。初始条件被”遗忘”了。

直觉解释

为什么不可约 + 非周期就能保证收敛？

想象一滴墨水滴入一杯水。如果杯中没有隔板（不可约），墨水最终能扩散到每一处。如果水没有规律性振荡（非周期），扩散过程不会产生持续的浓度脉动。最终墨水均匀分布——这就是稳态。

更数学地说：不可约保证了稳态分布的唯一性（只有一个”吸引子”），非周期保证了收敛而非振荡。如果链是不可约但有周期 $d > 1$，则 $P$ 有 $d$ 个模为 1 的特征值（$d$ 次单位根 $e^{2\pi i k/d}$），分布会在 $d$ 个”相”之间循环而不收敛到单个稳态。

关于证明：Perron-Frobenius 定理的完整证明需要较多准备工作，超出本文范围。感兴趣的读者可以参考 Levin, Peres & Wilmer 的 Markov Chains and Mixing Times 第 1 章和第 4 章。核心思路是利用矩阵 $P$ 的非负性和不可约性，证明主特征向量的分量全为正，然后利用非周期性排除单位圆上的其他特征值。

数值例子：手算 3×3 稳态分布

让我们用天气模型的转移矩阵做一个完整的手算。

$P = \begin{bmatrix} 0.2 & 0.6 & 0.2 \\ 0.3 & 0.3 & 0.4 \\ 0.5 & 0.1 & 0.4 \end{bmatrix}$

验证行随机性

• 第一行：$0.2 + 0.6 + 0.2 = 1$ ✓
• 第二行：$0.3 + 0.3 + 0.4 = 1$ ✓
• 第三行：$0.5 + 0.1 + 0.4 = 1$ ✓

所有元素非负 ✓。$P$ 是行随机矩阵。

验证不可约性

所有 $P_{ij} > 0$（矩阵的每个元素都是正的），所以从任意状态可以一步到达任意状态——不可约 ✓。

验证非周期性

$P_{11} = 0.2 > 0$（状态 A 有自环）——非周期 ✓。

由 Perron-Frobenius 定理，稳态分布存在且唯一。

求稳态分布

稳态方程 $\boldsymbol{\pi}^* P = \boldsymbol{\pi}^*$ 加上归一化条件 $\pi_1 + \pi_2 + \pi_3 = 1$：

$\begin{cases} 0.2\pi_1 + 0.3\pi_2 + 0.5\pi_3 = \pi_1 \\ 0.6\pi_1 + 0.3\pi_2 + 0.1\pi_3 = \pi_2 \\ 0.2\pi_1 + 0.4\pi_2 + 0.4\pi_3 = \pi_3 \\ \pi_1 + \pi_2 + \pi_3 = 1 \end{cases}$

整理前三个方程：

$\begin{cases} -0.8\pi_1 + 0.3\pi_2 + 0.5\pi_3 = 0 \\ 0.6\pi_1 - 0.7\pi_2 + 0.1\pi_3 = 0 \\ 0.2\pi_1 + 0.4\pi_2 - 0.6\pi_3 = 0 \end{cases}$

注意：这三个方程线性相关（因为 $P$ 的特征值 1 对应的特征空间至少是一维的）。所以我们用前两个方程加归一化条件求解。

从第一个方程：$\pi_1 = \frac{0.3\pi_2 + 0.5\pi_3}{0.8} = 0.375\pi_2 + 0.625\pi_3$

代入第二个方程：

$0.6(0.375\pi_2 + 0.625\pi_3) - 0.7\pi_2 + 0.1\pi_3 = 0$ $0.225\pi_2 + 0.375\pi_3 - 0.7\pi_2 + 0.1\pi_3 = 0$ $-0.475\pi_2 + 0.475\pi_3 = 0$ $\pi_2 = \pi_3$

令 $\pi_2 = \pi_3 = k$，则 $\pi_1 = 0.375k + 0.625k = k$。

归一化：$k + k + k = 1$，得 $k = \frac{1}{3}$。

$\boldsymbol{\pi}^* = \left(\frac{1}{3}, \frac{1}{3}, \frac{1}{3}\right) \approx (0.3333, 0.3333, 0.3333)$

验证

$\boldsymbol{\pi}^* P = \frac{1}{3}\begin{bmatrix}1 & 1 & 1\end{bmatrix}\begin{bmatrix} 0.2 & 0.6 & 0.2 \\ 0.3 & 0.3 & 0.4 \\ 0.5 & 0.1 & 0.4 \end{bmatrix} = \frac{1}{3}\begin{bmatrix}1.0 & 1.0 & 1.0\end{bmatrix} = \boldsymbol{\pi}^* \quad ✓$

逐项验证第一个分量：$\frac{1}{3}(0.2 + 0.3 + 0.5) = \frac{1}{3}(1.0) = \frac{1}{3}$ ✓

这个特殊结果的原因：稳态恰好是均匀分布，是因为 $P$ 的每一列之和也恰好为 1（$0.2 + 0.3 + 0.5 = 1$，$0.6 + 0.3 + 0.1 = 1$，$0.2 + 0.4 + 0.4 = 1$）。这种行和、列和都为 1 的矩阵称为双随机矩阵（doubly stochastic matrix），其稳态分布总是均匀分布。这不是巧合——它是 Birkhoff 定理的一个推论。

特征值的完整计算

为了理解收敛速度，我们需要 $P$ 的全部特征值。特征多项式为：

$\det(P - \lambda I) = 0$

展开 $3 \times 3$ 行列式（利用行和为 1 的性质，我们已知 $\lambda_1 = 1$ 是一个根）。特征多项式为 $\lambda^3 - 0.9\lambda^2 - 0.06\lambda - 0.04 = 0$，提取 $(\lambda - 1)$ 因子后：

$p(\lambda) = (\lambda - 1)(\lambda^2 + 0.1\lambda + 0.04) = 0$

求解 $\lambda^2 + 0.1\lambda + 0.04 = 0$：

$\lambda = \frac{-0.1 \pm \sqrt{0.01 - 0.16}}{2} = \frac{-0.1 \pm \sqrt{-0.15}}{2} = -0.05 \pm i\frac{\sqrt{0.15}}{2}$

判别式为负——两个根是共轭复数：

$\lambda_2 \approx -0.05 + 0.1936i, \quad \lambda_3 \approx -0.05 - 0.1936i$

所以三个特征值为：

$\lambda_1 = 1, \quad \lambda_{2,3} = -0.05 \pm 0.1936i$

验证：$\lambda_1 + \lambda_2 + \lambda_3 = 1 + (-0.05 + 0.1936i) + (-0.05 - 0.1936i) = 0.9 = \text{tr}(P) = 0.2 + 0.3 + 0.4$ ✓

两个复特征值的模相同：$|\lambda_2| = |\lambda_3| = \sqrt{0.05^2 + 0.1936^2} = \sqrt{0.0025 + 0.0375} = \sqrt{0.04} = 0.2$。

复特征值的含义：复特征值意味着系统在收敛过程中有振荡行为——分布不是单调趋近稳态，而是以衰减的”螺旋”方式逼近。每一步，非稳态分量的模乘以 $|\lambda_2| = 0.2$（快速衰减），同时方向旋转（振荡）。

第二大特征值的模为 $|\lambda_2| = 0.2$，这个值决定了收敛速度。

混合时间：第二大特征值的角色

$P^n$ 的特征分解

回忆 Art. 2 特征分解中的核心公式：如果 $P$ 可对角化为 $P = Q\Lambda Q^{-1}$，则：

$P^n = Q\Lambda^n Q^{-1} = Q\,\text{diag}(\lambda_1^n, \lambda_2^n, \ldots, \lambda_k^n)\,Q^{-1}$

对于行随机矩阵，$\lambda_1 = 1$，其余 $|\lambda_i| < 1$（Perron-Frobenius）。所以当 $n \to \infty$ 时：

$\Lambda^n = \text{diag}(1^n, \lambda_2^n, \lambda_3^n, \ldots) \to \text{diag}(1, 0, 0, \ldots)$

只有第一个分量存活，其余全部衰减到零。这就是为什么系统收敛到稳态——非稳态方向的分量指数衰减消失。

收敛速度

非稳态分量的衰减速率由它们对应的特征值决定。第 $i$ 个分量在 $n$ 步后的大小正比于 $|\lambda_i|^n$。因此，整体收敛速率由衰减最慢的非稳态分量决定，即：

$\text{收敛速率} \sim |\lambda_{\max}|^n, \quad \text{其中 } |\lambda_{\max}| = \max_{i \geq 2} |\lambda_i|$

定义谱隙（spectral gap）：

$\gamma = 1 - |\lambda_{\max}|$

谱隙越大，$|\lambda_{\max}|$ 越小，收敛越快。

混合时间

混合时间（mixing time）$t_{\text{mix}}$ 是使分布”足够接近”稳态所需的步数。形式化定义（使用全变差距离 total variation distance）：

$t_{\text{mix}}(\epsilon) = \min\left\{t : \max_{\boldsymbol{\pi}_0} \|\boldsymbol{\pi}_0 P^t - \boldsymbol{\pi}^*\|_{TV} \leq \epsilon\right\}$

其中全变差距离 $\|p - q\|_{TV} = \frac{1}{2}\sum_i |p_i - q_i|$。通常取 $\epsilon = 1/4$。

关键定理（Levin, Peres & Wilmer, Theorem 12.3, 12.4）：混合时间与谱隙的关系为：

$\frac{1}{\gamma}\left(\frac{1}{2}\ln\frac{1}{2\epsilon}\right) \leq t_{\text{mix}}(\epsilon) \leq \frac{1}{\gamma}\ln\left(\frac{n}{\epsilon}\right)$

其中 $n$ 是状态数，$\gamma = 1 - |\lambda_{\max}|$ 是谱隙。

逐项理解：

• 下界：$t_{\text{mix}} \geq \Omega(1/\gamma)$——混合时间至少与 $1/\gamma$ 同阶
• 上界：$t_{\text{mix}} \leq O(\frac{1}{\gamma}\ln n)$——至多差一个 $\ln n$ 因子
• 核心：$t_{\text{mix}} \approx \frac{1}{\gamma} = \frac{1}{1 - |\lambda_{\max}|}$

直觉：每一步转移，非稳态分量乘以 $|\lambda_{\max}|$，即缩减了 $1 - |\lambda_{\max}| = \gamma$ 的比例。要让分量从 1 衰减到 $\epsilon$，需要大约 $\ln(1/\epsilon)/\gamma$ 步。这与 $e^{-\gamma t} = \epsilon$ 解出 $t = \ln(1/\epsilon)/\gamma$ 一致。

天气模型的混合时间

对我们的例子，$|\lambda_{\max}| = 0.2$，谱隙 $\gamma = 0.8$。

$t_{\text{mix}}(1/4) \leq \frac{1}{0.8}\ln\left(\frac{3}{1/4}\right) = \frac{1}{0.8}\ln(12) \approx \frac{2.485}{0.8} \approx 3.1$

大约 3 步就能混合——这是一个”快速混合”的链。谱隙很大（$\gamma = 0.8$），意味着非稳态分量衰减迅速——每一步非稳态分量缩减到原来的 $|\lambda_2| = 0.2$，即减少 80%。

让我们验证：从 $\boldsymbol{\pi}_0 = (1, 0, 0)$（确定在状态 A）出发：

$t$	$\pi_A$	$\pi_B$	$\pi_C$	$\|\boldsymbol{\pi}_t - \boldsymbol{\pi}^*\|_{TV}$
0	1.0000	0.0000	0.0000	0.667
1	0.2000	0.6000	0.2000	0.267
2	0.3200	0.3200	0.3600	0.027
3	0.3400	0.3240	0.3360	0.009
4	0.3332	0.3348	0.3320	0.002

确实在 4 步左右就非常接近稳态了。

可视化：马尔可夫链状态转移

下面的交互组件让你亲手体验马尔可夫链的收敛过程。你可以编辑转移矩阵的概率值（会自动归一化），然后观察分布随迭代步数的变化。

马尔可夫链状态转移动画

转移矩阵 P（可编辑，自动归一化）

	→ A	→ B	→ C
A →
B →
C →

播放重置

t =0

探索建议：

1. 快速混合 vs 慢速混合：将某些转移概率设为接近 0，观察谱隙如何变小、收敛如何变慢
2. 几乎不可约：设置 $P = \begin{bmatrix}0.9&0.1&0\\0&0.9&0.1\\0.1&0&0.9\end{bmatrix}$，观察稳态分布和收敛速度
3. 双随机矩阵：确保每列之和也为 1，验证稳态分布是否为均匀分布
4. 吸收状态：设置某一行为 $(0, 0, 1)$（状态 C 是吸收的），观察系统最终全部流向 C

Part 1 工具的回顾：特征分解直接给出稳态

让我们退后一步，从更宏观的视角审视我们做了什么。

在 Part 1 中，Art. 2 特征分解建立了核心工具：任何可对角化的方阵 $A$ 都能分解为 $A = Q\Lambda Q^{-1}$，进而 $A^n = Q\Lambda^n Q^{-1}$。当时我们列出了应用清单，其中一条是”马尔可夫链的长期行为”。

现在这个应用完全展开了：

1. 对角化 $P = Q\Lambda Q^{-1}$
2. 取幂 $P^n = Q\,\text{diag}(1, \lambda_2^n, \ldots, \lambda_k^n)\,Q^{-1}$
3. 取极限 $n \to \infty$：$|\lambda_i| < 1$ 的分量衰减，只有 $\lambda_1 = 1$ 的分量存活
4. 稳态 = $\lambda_1 = 1$ 对应的左特征向量（归一化后）

同一个工具，新的语境，更深的结论。 Part 1 的特征分解是通用的——它对任何方阵都能用。但当矩阵有随机矩阵的额外结构（非负、行和为 1）时，Perron-Frobenius 定理提供了额外保证：$\lambda_1 = 1$ 是严格主特征值，稳态分布唯一且所有分量为正。

这正是 Art. 14 算子全景 的核心主题：Part 2 不是一套新数学，而是同一套工具遇到有特殊结构的矩阵时，产生的更强结论。

马尔可夫链在 ML 中的应用

MCMC 采样

马尔可夫链蒙特卡罗（Markov Chain Monte Carlo, MCMC）是贝叶斯机器学习中最重要的采样方法之一。核心思想：构造一个马尔可夫链，使其稳态分布恰好是我们想采样的目标分布。

经典的 Metropolis-Hastings 算法：

1. 从当前状态 $x$ 提议一个新状态 $x'$
2. 以概率 $\alpha = \min\left(1, \frac{p(x')q(x|x')}{p(x)q(x'|x)}\right)$ 接受提议
3. 如果接受，转移到 $x'$；否则留在 $x$

其中 $p$ 是目标分布，$q$ 是提议分布。关键保证：这样构造的转移矩阵满足细致平衡条件（detailed balance）$\pi^*_i P_{ij} = \pi^*_j P_{ji}$，从而 $\boldsymbol{\pi}^*$ 确实是稳态分布。混合时间 $t_{\text{mix}}$ 决定了采样效率——混合越快，需要的”烧入期”（burn-in）越短。（参考 Andrieu et al., 2003）

文本生成

语言模型的自回归生成过程也可以视为一种马尔可夫过程（虽然实际的 transformer 有更长的上下文依赖）。在最简单的 $n$-gram 语言模型中，下一个词的分布只取决于前 $n-1$ 个词——这正是马尔可夫性。转移矩阵的每一行是一个词汇表上的条件概率分布。

强化学习

强化学习中的马尔可夫决策过程（Markov Decision Process, MDP）是马尔可夫链的推广：在每个状态，智能体选择一个动作，然后按转移概率进入下一个状态。给定固定策略后，状态转移就是一个标准的马尔可夫链，其稳态分布（如果存在）描述了智能体的长期行为。

总结与展望

本文从 Part 2 最简单的算子矩阵——马尔可夫链的转移矩阵——出发，展示了 Part 1 特征分解工具在算子语境下的核心应用：

• 转移矩阵 $P$ 是行随机矩阵：非负、行和为 1，每行是一个概率分布
• 矩阵乘法 = 概率传播：$\boldsymbol{\pi}_{t+1} = \boldsymbol{\pi}_t P$，乘一次就是执行一步
• 稳态分布 = 特征值 1 对应的左特征向量，直接由特征分解给出
• Perron-Frobenius 定理：不可约 + 非周期的随机矩阵有唯一稳态，$\lambda_1 = 1$ 是严格主特征值
• 混合时间由谱隙 $\gamma = 1 - |\lambda_2|$ 控制：谱隙越大，收敛越快，$t_{\text{mix}} \approx 1/\gamma$

下一篇，我们问一个自然的追问：如果状态看不到了呢？ 在马尔可夫链中，我们假设状态是直接可观测的。但如果系统的真实状态是隐藏的，我们只能通过带噪声的观测来间接推断——这就是隐马尔可夫模型（Hidden Markov Model, HMM）。从概念地图的第一列移到第二列，从”可观测”到”隐藏”，数学复杂度陡增，但转移矩阵 $P$ 仍然是核心。