马尔可夫链 · aiwiki.page

马尔可夫链是一种随机过程，其中未来状态的条件概率取决于当前状态，而不取决于完整的历史。它以数学家安德烈·马尔可夫的名字命名，为研究相互依赖的随机结果序列提供了框架。标准的离散时间形式描述相邻时间步之间的状态转移；连续时间马尔可夫链则描述在随机时刻发生的状态转移。马尔可夫链将概率建模与矩阵方法及长期行为分析联系起来。(math.dartmouth.edu)

定义与马尔可夫性质

离散时间马尔可夫链是一个随机变量序列 $X_0,X_1,\ldots$ ，其取值属于状态空间 $S$ ，该空间通常是有限集或可数无限集。定义马尔可夫链的马尔可夫性质为

\Pr(X_{n+1}=j\mid X_0=i_0,\ldots,X_n=i) =\Pr(X_{n+1}=j\mid X_n=i),

只要作为条件的事件具有正概率，上式就成立。这表达了条件独立：一旦当前状态已知，更早的状态就不再提供有关下一状态的额外信息。这并不意味着相邻状态相互独立，也不意味着过程必须始终保持不变。(math.dartmouth.edu)

如果一条链的转移概率不依赖于 $n$ ，就称其为时间齐次的；否则称为时间非齐次的。齐次性涉及转移规则，而平稳性涉及过程的分布；齐次链的初始分布不一定是平稳分布。所选的状态必须概括预测所需的信息，因此马尔可夫假设是否成立，取决于如何表示这个系统。(see.stanford.edu)

转移矩阵与示例

对于齐次链，定义 $p_{ij}=\Pr(X_{n+1}=j\mid X_n=i)$ 。这些概率构成一个转移矩阵 $P=(p_{ij})$ ，它是一个元素非负且每行元素之和均为一的矩阵。转移矩阵与初始分布 $\mu_0$ 共同确定这条链的概率规律。采用行向量表示时，

\mu_n=\mu_0P^n.

矩阵元素 $(P^n)_{ij}$ 给出从 $i$ 出发、经过 $n$ 步后到达 $j$ 的概率。查普曼–柯尔莫哥洛夫方程表达了转移的复合关系： $P^{m+n}=P^mP^n$ 。(web.stanford.edu)

作为计算示例，假设一个简化的天气模型有晴天和雨天两个状态，其转移矩阵为

P= \begin{pmatrix} 0.8&0.2\\ 0.4&0.6 \end{pmatrix}.

从晴天出发，两步后下雨的概率为 $0.8(0.2)+0.2(0.6)=0.28$ ，计算中考虑了两种可能的中间状态。这是一个假设模型，并非基于实际观测的天气预报。

状态分类与长期行为

如果两个状态都能以正概率到达对方，就称它们互通。如果一条链的所有状态都互通，就称这条链为不可约的。一个状态的周期，是所有可能的正返回步数的最大公约数；如果不可约链的这一周期为一，就称它为非周期的。例如，在两个状态之间确定性交替的链，其周期为二。(ocw.mit.edu)

如果从某个状态出发，链最终以概率一返回该状态，就称该状态为常返状态；否则，它是暂留状态。如果常返状态的返回时间的期望值有限，就称其为正常返状态。吸收状态是指一旦进入便无法离开的状态。对于有限吸收马尔可夫链，若暂留状态对应的矩阵分块为 $Q$ ，且最终必然发生吸收，那么基本矩阵 $N=(I-Q)^{-1}$ 记录了吸收之前访问各暂留状态的期望次数。(math.dartmouth.edu)

平稳分布是满足下式的概率向量：

\pi=\pi P.

因此，如果以 $\pi$ 为初始分布，每一步的状态分布都会保持相同。用线性代数中特征值与特征向量的概念表述，它是对应于特征值一的、经过归一化的非负左特征向量。(ocw.mit.edu)

每条有限不可约链都有唯一的平稳分布。如果它还具有非周期性，那么无论初始分布是什么， $\mu_0P^n$ 都会收敛到该平稳分布。长期观测得到的各状态出现频率要收敛，并不要求非周期性。对于不可约的可数无限链，存在平稳概率分布的必要条件是正常返性。这些区别说明，平稳性、常返性和收敛性不能混为一谈。(web.mit.edu)

在上述天气模型中，求解 $\pi=\pi P$ 可得 $\pi=(2/3,1/3)$ 。因此，模型中雨天状态的长期出现频率为三分之一，而不是从某个特定状态出发一步后下雨的概率。

可逆性与计算

如果将时间方向反转后，平稳链的概率行为保持不变，就称它是可逆的。对于离散状态，细致平衡条件

\pi_i p_{ij}=\pi_j p_{ji},

刻画了可逆性，并蕴含平稳性。它要求每一对状态之间两个方向的概率流相等，这比总流入与总流出相平衡的条件更强。(ocw.mit.edu)

马尔可夫链蒙特卡罗方法通过构造转移规则，使其平稳分布成为所需的目标分布。其算法生成相互依赖的样本，用于估计与分布有关的量。细致平衡是常用的设计手段，但并非所有有效采样器都必须满足这一条件。相邻样本之间可能仍有很强的相关性，因此计算精度不仅取决于样本数量，也取决于对状态空间的探索情况及样本之间的相关性。(arxiv.org)

扩展与应用

有限状态空间上的连续时间马尔可夫链由生成矩阵 $G$ 描述，其非对角元素为非负的转移速率，每行元素之和为零。经过时间 $t$ 后的转移矩阵为 $e^{tG}$ ，平稳分布满足 $\pi G=0$ 。这类模型描述的系统，其状态转移不必遵循固定的观测时间间隔。(statslab.cam.ac.uk)

图上的随机游走是一种以顶点为状态的马尔可夫链。图上的随机游走可用于网络分析，包括PageRank。隐马尔可夫模型在未观测到的马尔可夫状态基础上，加入由这些状态生成的观测，支持语音识别等应用。马尔可夫决策过程进一步引入影响转移概率的动作，将这一框架从被动演化扩展到受控系统。(ocw.mit.edu)