本文最后更新于:2024年5月7日 下午
马尔可夫链是满足马尔可夫性质的随机过程,本文记录相关内容。
简介
马尔可夫链 $ 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$,有:
- 利用已知条件:
- 因此:
$$
\vec \pi {\bf{P}} = \vec \pi
$$
参考资料
文章链接:
https://www.zywvvd.com/notes/study/math/markov-chain/markov-chain/
“觉得不错的话,给点打赏吧 ୧(๑•̀⌄•́๑)૭”
微信支付
支付宝支付