马尔可夫链
概述
马尔可夫链（Markov Chain）由安德烈·马尔可夫于 1906 年提出，是一类具有马尔可夫性质（Markov property）的随机过程：给定当前状态，未来状态的条件分布与过去历史无关（"无记忆性"）。
$$P(X_{n+1} = j \mid X_n = i, X_{n-1}, \ldots, X_0) = P(X_{n+1} = j \mid X_n = i) = p_{ij}$$
其中 $p_{ij}$ 是从状态 $i$ 到状态 $j$ 的转移概率。马尔可夫链是 20 世纪最重要的数学模型之一，打破了经典概率论对独立性的依赖，开辟了随机过程理论。
关键内容
基本定义
转移矩阵 $P = (p_{ij})$：$p_{ij} \geq 0$，$\sum_j p_{ij} = 1$（每行之和为 1 的非负矩阵）。
平稳分布 $\pi$：满足 $\pi P = \pi$（$\pi$ 是转移矩阵的左特征向量，对应特征值 1）。由Perron-Frobenius定理，对不可约链，平稳分布唯一且所有分量为正。
重要性质
| 性质 | 含义 |
|---|---|
| 不可约（Irreducible） | 任意两状态之间可互相到达，对应不可约矩阵 |
| 非周期（Aperiodic） | 不存在强迫的周期性振荡 |
| 遍历（Ergodic） | 不可约+非周期 → 从任意初始分布收敛到唯一平稳分布 |
| 混合时间 | 趋近平稳分布的速率由谱间隙（$1- |
大数定律与马尔可夫链
马尔可夫的关键结果：对不可约遍历链，时间平均收敛于空间平均（平稳分布均值）——这是大数定律在依赖序列上的推广。
应用
| 领域 | 应用 |
|---|---|
| 物理 | 统计力学、Ising 模型 |
| 计算 | PageRank 算法（Google）、MCMC（托马斯·贝叶斯</td>
</tr>
<tr>
<td>语言</td>
<td>N-gram [[Language-Model</td>
</tr>
<tr>
<td>生物</td>
<td>基因频率演化（Wright-Fisher 模型）</td>
</tr>
<tr>
<td>金融</td>
<td>信用评级转移模型</td>
</tr>
</tbody>
</table>
<h3 id="pagerank">与 PageRank 的联系</h3>
<p>[[Google 的 PageRank 算法本质上是在超链接转移矩阵上求平稳分布——直接应用了Perron-Frobenius定理保证的 Perron 根 = 1 的左特征向量的存在唯一性。
来源
相关 |