马尔可夫链

本文最后更新于:2022年8月10日 上午

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

简介

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

  • 马尔可夫链的数学定义为:
    $$
    P\left(X_{t+1} \mid X_{t}, X_{t-1}, \cdots, X_{1}\right)=P\left(X_{t+1} \mid X_{t}\right)
    $$

马尔可夫链示例

设定

社会学家把人按照经济状况分成三类:下层、中层、上层。用状态 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

转移方式

使用矩阵的表示方式,转移概率矩阵记作:

$$ \mathbf{P}=\left[\begin{array}{lll}0.65 & 0.28 & 0.07 \\ 0.15 & 0.67 & 0.18 \\ 0.12 & 0.36 & 0.52\end{array}\right] $$

假设当前这一代人在下层、中层、上层的人的比例是概率分布 $ \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 代人的分布状况:

编号 阶层1 阶层2 阶层3
0 0.72 0.19 0.09
1 0.5073 0.3613 0.1314
2 0.399708 0.431419 0.168873
3 0.344788 0.461763 0.193449
4 0.31659 0.475564 0.207846
5 0.30206 0.482097 0.215843
6 0.294555 0.485285 0.22016
7 0.290673 0.486874 0.222453
8 0.288663 0.487677 0.22366
9 0.287622 0.488087 0.224292
10 0.287082 0.488297 0.224621
11 0.286802 0.488406 0.224792
12 0.286657 0.488462 0.224881
13 0.286582 0.48849 0.224927
14 0.286543 0.488505 0.224951

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

数据2

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

编号 阶层1 阶层2 阶层3
0 0.51 0.34 0.15
1 0.4005 0.4246 0.1749
2 0.345003 0.459586 0.195411
3 0.316639 0.474871 0.208489
4 0.302065 0.481879 0.216056
5 0.294551 0.485217 0.220232
6 0.290668 0.486853 0.222478
7 0.28866 0.487671 0.223669
8 0.28762 0.488085 0.224295
9 0.287081 0.488297 0.224622
10 0.286802 0.488406 0.224793
11 0.286657 0.488462 0.224881
12 0.286582 0.488491 0.224927
13 0.286543 0.488505 0.224951
14 0.286523 0.488513 0.224964

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

收敛原因

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

平稳分布

马尔可夫链定理

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

$$ \lim _{n \rightarrow \infty} \mathbf{P}^{n}=\left[\begin{array}{ccccc}\pi(1) & \pi(2) & \cdots & \pi(j) & \cdots \\ \pi(1) & \pi(2) & \cdots & \pi(j) & \cdots \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ \pi(1) & \pi(2) & \cdots & \pi(j) & \cdots \\ \vdots & \vdots & \ddots & \vdots & \vdots\end{array}\right] \\ \pi(j)=\sum_{i=0}^{\infty} \pi(i) P_{i, j} $$

其中:

  • $ 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} $, 则有:

$$ \begin{array}{c} X_{0} \sim \vec{\pi}_{0} \\ X_{1} \sim \vec{\pi}_{1} \\ \ldots \\ X_{n} \sim \vec{\pi}_{n} \\ X_{n+1} \sim \vec{\pi}_{n+1} \end{array} $$

假设到达第$n$​​步时,马尔可夫链收敛,则有:

$$ X_{n} \sim \vec{\pi}\\ X_{n+1} \sim \vec{\pi}\\ ... $$

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

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

$$
x_{0}, x_{1}, \cdots, x_{n}, x_{q_{b}+1}, \cdots
$$

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

平稳分布

细致平稳条件定理

如果非周期马尔可夫链的转移矩阵$P$和某个分布$\vec{\pi}$​ 满足:
$$
\pi(i) P_{i, j}=\pi(j) P_{j, i}
$$

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

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

证明

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

$$ \begin{array}{l} \vec \pi {\bf{P}} &= [{\pi _1},{\pi _2},...,{\pi _i},...,{\pi _n}]\left( {\begin{array}{*{20}{c}} \begin{array}{l} \\ \end{array}&\begin{array}{l} {P_{1i}}\\ {P_{2i}} \end{array}&\begin{array}{l} \\ \end{array}\\ {...}&{{P_{3i}}}&{...}\\ \begin{array}{l} \\ \end{array}&\begin{array}{l} ...\\ {P_{ni}} \end{array}&\begin{array}{l} \\ \end{array} \end{array}} \right)\\ &= [...,{\pi _1}{P_{1i}} + {\pi _2}{P_{2i}} + \cdots + {\pi _n}{P_{ni}},...] \end{array} $$
  • 我们需要证明对于任意的$i$​​,有:
$$ {\pi _i} = {\pi _1}{P_{1i}} + {\pi _2}{P_{2i}} + \cdots + {\pi _n}{P_{ni}} $$
  • 利用已知条件:
$$ \begin{array}{l} {\pi _1}{P_{1i}} + {\pi _2}{P_{2i}} + \cdots + {\pi _n}{P_{ni}} &= {\pi _i}{P_{i1}} + {\pi _i}{P_{i2}} + \cdots + {\pi _i}{P_{in}}\\ &= {\pi _i}\sum\limits_{j = 1}^n {{P_{ij}}} \\ & = {\pi _i} \end{array} $$
  • 因此:

$$
\vec \pi {\bf{P}} = \vec \pi
$$

参考资料


马尔可夫链
https://www.zywvvd.com/notes/study/math/markov-chain/markov-chain/
作者
Yiwei Zhang
发布于
2021年8月1日
许可协议