马尔可夫链

马尔可夫链是满足马尔可夫性质的随机过程，本文记录相关内容。

简介

马尔可夫链 X_{1}, X_{2}, \cdots 描述了一个状态序列，其中每个状态值取决于前一个状态。 X_{t} 为随机变量, 称为时刻 t 的状态, 其取值范围称作状态空间。

• 马尔可夫链的数学定义为:

马尔可夫链示例

设定

社会学家把人按照经济状况分成三类：下层、中层、上层。用状态 1,2,3 代表着三个阶层。社会学家发现：决定一个人的收入阶层的最重要因素就是其父母的收入阶层。

• 如果一个人的收入属于下层，则他的孩子属于下层的概率是 0.65，属于中层的概率是 0.28，属于上层的概率是 0.07 。
• 如果一个人的收入属于中层，则他的孩子属于下层的概率是 0.15，属于中层的概率是 0.67，属于上层的概率是 0.18 。
• 如果一个人的收入属于上层，则他的孩子属于下层的概率是 0.12，属于中层的概率是 0.36，属于上层的概率是 0.52 。 从父代到子代，收入阶层的变化的转移概率如下： 子代阶层1 子代阶层2 子代阶层3 父代阶层1 0.65 0.28 0.07 父代阶层2 0.15 0.67 0.18 父代阶层3 0.12 0.36 0.52

转移方式

使用矩阵的表示方式，转移概率矩阵记作：

假设当前这一代人在下层、中层、上层的人的比例是概率分布 \vec{\pi}_{0}=\left(\pi_{0}(1), \pi_{0}(2), \pi_{0}(3)\right) ，则：

• 他们的子女在下层、中层、上层的人的概率分布是 \vec{\pi}_{1}=\left(\pi_{1}(1), \pi_{1}(2), \pi_{1}(3)\right)=\vec{\pi}_{0} \mathbf{P}
• 他们的孙子代的分布比例将是 \vec{\pi}_{2}=\left(\pi_{2}(1), \pi_{2}(2), \pi_{2}(3)\right)=\vec{\pi}_{1} \mathbf{P}=\vec{\pi}_{0} \mathbf{P}^{2}
• ……
• 第 n 代子孙在下层、中层、上层的人的比例是 \vec{\pi}_{n}=\left(\pi_{n}(1), \pi_{n}(2), \pi_{n}(3)\right)=\vec{\pi}_{n-1} \mathbf{P}=\vec{\pi}_{0} \mathbf{P}^{n}

数据举例

数据1

假设初始概率分布为 \pi_{0}=(0.72,0.19,0.09) ​ ，给出前 14 代人的分布状况：

可以看到从第 9 代开始，阶层分布就趋向于稳定不变。

数据2

如果换一个初始概率分布为 \vec{\pi}_{0}=(0.51,0.34,0.15) ​ ，给出前 14 代人的分布状况：

可以发现到第 8 代又收敛了。

收敛原因

两次不同的初始概率分布，最终都收敛到概率分布 \vec{\pi}=(0.286,0.489,0.225) 。 这说明收敛的行为和初始概率分布{\vec{\pi}}_0无关，而是由概率转移矩阵P决定的。

平稳分布

马尔可夫链定理

如果一个非周期马尔可夫链具有转移概率矩阵P​ ，且它的任何两个状态是联通的，则有：

其中:

• 1,2, \cdots, j, \cdots ​ 为所有可能的状态。
• P_{i,j}是转移概率矩阵P的第i行第j列的元素，表示状态i转移到状态j的概率。
• 概率分布 \vec{\pi} 是方程 \vec{\pi} \mathbf{P}=\vec{\pi} 的唯一解，其中 \vec{\pi}=(\pi(1), \pi(2), \cdots, \pi(j), \cdots), \sum_{j=0}^{\infty} \pi(j)=\mathbf{1} 。 称概率分布 \vec{\pi} ​ 为马尔可夫链的平稳分布。

在马尔可夫链定理中：

• 马尔可夫链的状态不要求有限, 可以是无穷多个。
• 非周期性在实际任务中都是满足的。
• 两个状态的连通指的是：状态 i ​ 可以通过有限的 n ​ 步转移到达 j ​ (并不要求从状态 i ​ 可以直接一步转移到 状态 j ​ )。 零。

收敛

从初始概率分布 \vec{\pi}_{0} 出发, 在马尔可夫链上做状态转移, 记时刻 i 的状态 X_{i} 服从的概率分布为 \vec{\pi}_{i} , 记作 X_{i} \sim \vec{\pi}_{i} , 则有:

假设到达第n​​步时，马尔可夫链收敛，则有：

所以 X_{n}, X_{n+1}, X_{n+2}, \cdots ​是同分布的随机变量（当然它们并不独立）。

如果从一个具体的初始状态x_0开始，然后沿着马尔可夫链按照概率转移矩阵做调整，则得到一个转移序列

根据马尔可夫链的收敛行为，当n​​较大时， x_{n}, x_{n+1}, \cdots ​​将是平稳分布\vec{\pi}​​​的样本。

平稳分布

细致平稳条件定理

​ 满足：

则 \vec{\pi} 是马尔可夫链的平稳分布，这也是马尔可夫细致平稳条件。

这被称作马尔可夫链的细致平稳条件 detailed balance condition

证明

已知 \pi(i) P_{i, j}=\pi(j) P_{j, i}​​​ ,往证 \vec \pi {\bf{P}} = \vec \pi ​

• 我们需要证明对于任意的i​​，有：

• 利用已知条件：

• 因此：

参考资料

• http://www.huaxiaozhuan.com/数学基础/chapters/4_monte_carlo.html