2022-04-02

数学建模实验 VI Markov Chain

Author: `sandyzikun`

简单介绍 Markov Chain.

Problem Description

在英国, 保守党成员的第二代加入保守党的概率为0.7, 加入工党的概率为0.2, 加入自由党的概率为0.1; 工党成员的第二代加入保守党的概率为0.4, 加入工党的概率为0.5, 加入自由党的概率为0.1; 而自由党成员的第二代加入保守党的概率为0.2, 加入工党的概率为0.4, 加入自由党的概率为0.4.
试建立模型, 解决以下问题:

求出自由党成员的第三代加入工党的概率;
在经过较长的时间后, 各党成员的后代加入各党派的概率分布是否具有稳定性?
用试验说明, 影响第2问中, 概率分布稳定性的主要因素.

Modeling

Markov链(马尔可夫链,马尔科夫链) ¹ 是一种状态转移模型, 其用于描述具有无后效性且存在于离散的指数集合(Index Set)与状态空间(State Space)内的随机过程(Stochastic Process).

(如上图所示便是天气状况沿Markov链进行的状态转移模型)

无后效性 (Without Aftereffect) ² 又称为Markov性质(Markov Property)³, 是概率论中的一个重要概念, 指某一随机过程在给定此刻状态以及过往所有状态的情况下, 其未来状态的条件概率分布依赖且仅依赖于此刻状态, 即其与过往状态均为条件独立的, 则称此随机过程具有 Markov性质, 具有这样性质的随机过程被称为 Markov过程, 可以认为 $ \forall 确定的 \tau $ 都有

$\Pr(X_{\tau + 1} | X_0, \cdots, X_{\tau - 1}, X_{\tau}) \equiv \Pr(X_{\tau + 1} | X_{\tau})$

或者更简单地表述为, 已知此刻, 未来与过往无关, 这一点在动态规划(Dynamic Programming)⁴中也有广泛应用.

以如上所述的情况为例, 我们可以得到状态转移概率的列表

父母所属党派 \ 子女所属党派	保守党	工党	自由党
保守党	`0.7`	`0.2`	`0.1`
工党	`0.4`	`0.5`	`0.1`
自由党	`0.2`	`0.4`	`0.4`

State Transition Theory

根据上表, 我们可以得到 状态转移矩阵 (State Transition Matrix) 如下

$P = \begin{bmatrix} 0.7 & 0.2 & 0.1 \\ 0.4 & 0.5 & 0.1 \\ 0.2 & 0.4 & 0.4 \\ \end{bmatrix}$

这个状态转移矩阵由上一状态向下一状态各个情况的概率组成, 每一行矢量表示某确定的上一状态转向不同的下一状态的各个概率.

因此假设我们某人此刻加入三个党派的概率为 $ \alpha = (p_1, p_2, p_3) $, 那么根据前文所述, 其子女加入三个党派的概率便分别为

$\begin{pmatrix} 0.7 p_1 + 0.4 p_2 + 0.2 p_3 \\ 0.2 p_1 + 0.5 p_2 + 0.4 p_3 \\ 0.1 p_1 + 0.1 p_2 + 0.4 p_3 \\ \end{pmatrix}^T$

因此如若像这样把某人加入三个党派的概率排成一个行矢量 $ \alpha_0 = (p_1, p_2, p_3) $, 则其子女加入三个党派的概率可以写为

$\alpha_1 = \alpha_0 P$

第m代子女加入三个党派的概率可以写为

$\alpha_m = \alpha_0 P^m$

对比可知, 如若把m代过程视为一次状态转移, 则这样一次的状态转移的矩阵便是 $ P^m $.

值得一提的是, 由于 $ \alpha_0 $ 中的 $ p_1 $, $ p_2 $, $ p_3 $ 三个分量之和为1, 所以 $ \alpha_1 = \alpha_0 P $ 的三个分量共九项之和仍为1, 以此类推 $ \forall \tau, \alpha_{\tau} $ 的三个分量恒为1, 这满足了永远是这三个分量对应的三个事件组成全事件的这一事实.

Convergency

现在来考虑随机过程沿Markov链不断状态转移的收敛性(Convergency), 但在讲解之前先考虑1次, 2次, …, m次状态转移之后的状态转移矩阵 $ P, P^2, \cdots, P^m $.

根据题目中所给定的概率, 我们创建存储一次状态转移的矩阵变量p_trans

Python

import numpy as np

p_trans = np.array([
    [ .7, .2, .1 ],
    [ .4, .5, .1 ],
    [ .2, .4, .4 ],
    ])

接下来我们审察其多次乘方的结果, 即多次状态转移所对用的矩阵

Python

p_cur = p_trans.copy()

print("P^01:", "[%s, %s, %s]" % tuple(p_cur))
for k in range(39):
    p_cur = p_cur @ p_trans
    print("P^%02d:" % (k + 2), "[%s, %s, %s]" % tuple(p_cur))

输出如下

P^01: [[0.7 0.2 0.1], [0.4 0.5 0.1], [0.2 0.4 0.4]]
P^02: [[0.59 0.28 0.13], [0.5  0.37 0.13], [0.38 0.4  0.22]]
P^03: [[0.551 0.31  0.139], [0.524 0.337 0.139], [0.47  0.364 0.166]]
P^04: [[0.5375 0.3208 0.1417], [0.5294 0.3289 0.1417], [0.5078 0.3424 0.1498]]
P^05: [[0.53291 0.32458 0.14251], [0.53048 0.32701 0.14251], [0.52238 0.33268 0.14494]]
P^06: [[0.531371 0.325876 0.142753], [0.530642 0.326605 0.142753], [0.527726 0.328792 0.143482]]
P^07: [[0.5308607 0.3263134 0.1428259], [0.530642  0.3265321 0.1428259], [0.5296214 0.327334  0.1430446]]
P^08: [[0.53069303 0.3264592  0.14284777], [0.53062742 0.32652481 0.14284777], [0.5302775  0.32680912 0.14291338]]
P^09: [[0.53063836 0.32650731 0.14285433], [0.53061867 0.326527   0.14285433], [0.53050057 0.32662541 0.14287401]]
P^10: [[0.53062064 0.32652306 0.1428563 ], [0.53061474 0.32652897 0.1428563 ], [0.53057537 0.32656243 0.1428622 ]]
P^11: [[0.53061493 0.32652818 0.14285689], [0.53061316 0.32652995 0.14285689], [0.53060017 0.32654117 0.14285866]]
P^12: [[0.5306131  0.32652983 0.14285707], [0.53061257 0.32653036 0.14285707], [0.53060832 0.32653408 0.1428576 ]]
P^13: [[0.53061252 0.32653036 0.14285712], [0.53061236 0.32653052 0.14285712], [0.53061098 0.32653174 0.14285728]]
P^14: [[0.53061233 0.32653053 0.14285714], [0.53061228 0.32653058 0.14285714], [0.53061184 0.32653098 0.14285718]]
P^15: [[0.53061227 0.32653059 0.14285714], [0.53061226 0.3265306  0.14285714], [0.53061211 0.32653073 0.14285716]]
P^16: [[0.53061225 0.3265306  0.14285714], [0.53061225 0.32653061 0.14285714], [0.5306122  0.32653065 0.14285715]]
P^17: [[0.53061225 0.32653061 0.14285714], [0.53061225 0.32653061 0.14285714], [0.53061223 0.32653062 0.14285714]]
P^18: [[0.53061225 0.32653061 0.14285714], [0.53061225 0.32653061 0.14285714], [0.53061224 0.32653062 0.14285714]]
P^19: [[0.53061225 0.32653061 0.14285714], [0.53061225 0.32653061 0.14285714], [0.53061224 0.32653061 0.14285714]]
P^20: [[0.53061224 0.32653061 0.14285714], [0.53061224 0.32653061 0.14285714], [0.53061224 0.32653061 0.14285714]]
P^21: [[0.53061224 0.32653061 0.14285714], [0.53061224 0.32653061 0.14285714], [0.53061224 0.32653061 0.14285714]]
P^22: [[0.53061224 0.32653061 0.14285714], [0.53061224 0.32653061 0.14285714], [0.53061224 0.32653061 0.14285714]]
P^23: [[0.53061224 0.32653061 0.14285714], [0.53061224 0.32653061 0.14285714], [0.53061224 0.32653061 0.14285714]]
P^24: [[0.53061224 0.32653061 0.14285714], [0.53061224 0.32653061 0.14285714], [0.53061224 0.32653061 0.14285714]]
P^25: [[0.53061224 0.32653061 0.14285714], [0.53061224 0.32653061 0.14285714], [0.53061224 0.32653061 0.14285714]]
P^26: [[0.53061224 0.32653061 0.14285714], [0.53061224 0.32653061 0.14285714], [0.53061224 0.32653061 0.14285714]]
P^27: [[0.53061224 0.32653061 0.14285714], [0.53061224 0.32653061 0.14285714], [0.53061224 0.32653061 0.14285714]]
P^28: [[0.53061224 0.32653061 0.14285714], [0.53061224 0.32653061 0.14285714], [0.53061224 0.32653061 0.14285714]]
P^29: [[0.53061224 0.32653061 0.14285714], [0.53061224 0.32653061 0.14285714], [0.53061224 0.32653061 0.14285714]]
P^30: [[0.53061224 0.32653061 0.14285714], [0.53061224 0.32653061 0.14285714], [0.53061224 0.32653061 0.14285714]]
P^31: [[0.53061224 0.32653061 0.14285714], [0.53061224 0.32653061 0.14285714], [0.53061224 0.32653061 0.14285714]]
P^32: [[0.53061224 0.32653061 0.14285714], [0.53061224 0.32653061 0.14285714], [0.53061224 0.32653061 0.14285714]]
P^33: [[0.53061224 0.32653061 0.14285714], [0.53061224 0.32653061 0.14285714], [0.53061224 0.32653061 0.14285714]]
P^34: [[0.53061224 0.32653061 0.14285714], [0.53061224 0.32653061 0.14285714], [0.53061224 0.32653061 0.14285714]]
P^35: [[0.53061224 0.32653061 0.14285714], [0.53061224 0.32653061 0.14285714], [0.53061224 0.32653061 0.14285714]]
P^36: [[0.53061224 0.32653061 0.14285714], [0.53061224 0.32653061 0.14285714], [0.53061224 0.32653061 0.14285714]]
P^37: [[0.53061224 0.32653061 0.14285714], [0.53061224 0.32653061 0.14285714], [0.53061224 0.32653061 0.14285714]]
P^38: [[0.53061224 0.32653061 0.14285714], [0.53061224 0.32653061 0.14285714], [0.53061224 0.32653061 0.14285714]]
P^39: [[0.53061224 0.32653061 0.14285714], [0.53061224 0.32653061 0.14285714], [0.53061224 0.32653061 0.14285714]]
P^40: [[0.53061224 0.32653061 0.14285714], [0.53061224 0.32653061 0.14285714], [0.53061224 0.32653061 0.14285714]]

我们可以发现, 从 $ P^{20} $ 起, 多次状态转移对应的矩阵皆为

$\begin{bmatrix} 0.53061224 & 0.32653061 & 0.14285714 \\ 0.53061224 & 0.32653061 & 0.14285714 \\ 0.53061224 & 0.32653061 & 0.14285714 \\ \end{bmatrix}$

其中每一个行矢量皆为

$\begin{pmatrix} 0.53061224 \\ 0.32653061 \\ 0.14285714 \\ \end{pmatrix}^T$

即此后后代加入各党派概率的分布律收敛如下:

加入党派 $ \xi $	保守党	工党	自由党
对应概率 $ \Pr(\xi) $	0.53061224	0.32653061	0.14285714

现在我们得到随机过程沿Markov链不断进行状态转移的收敛性质.⁵
如果一个非周期的马尔科夫链有状态转移矩阵P, 并且它的任何两个状态是连通的, 则有:

$\lim_{m \rightarrow \infty} P^m_{kl} = \pi_l, 且与k无关$
$\lim_{m \rightarrow \infty} P^m = \begin{bmatrix} \pi_1 & \pi_2 & \cdots & \pi_l & \cdots \\ \pi_1 & \pi_2 & \cdots & \pi_l & \cdots \\ \vdots & \vdots & \vdots & \vdots & \vdots \\ \pi_1 & \pi_2 & \cdots & \pi_l & \cdots \\ \end{bmatrix}$
$\pi_l = \sum_k \pi_k P_{kl}$
$\pi = (\pi_1, \pi_2, \cdots, \pi_l, \cdots)$
是无限多代收敛后的所有情况对应概率所组成的矢量, 称为Markov链的平稳分布 (Stationary Distribution) ⁶, 满足
$\sum_k \pi_k = 1$

需要注意的是:

非周期的马尔科夫链: 这个主要是指马尔科夫链的状态转化不是循环的, 如果是循环的则永远不会收敛…幸运的是我们遇到的马尔科夫链一般都是非周期性的.
用数学方式表述则是: 对于任意某一状态k, 如若
$\gcd\{m | m \ge 1, P^m_{kk} > 0\} = 1$
则该状态为非周期的;
任何两个状态是连通的: 这个指的是从任意一个状态可以通过有限步到达其他的任意一个状态, 不会出现条件概率一直为0导致不可达的情况;
马尔科夫链的状态数可以是有限的, 也可以是无限的.
因此可以用于连续概率分布和离散概率分布;

Solving

现在我们来考虑开篇提出的问题.

解: 根据Markov链的性质, 三次状态转移的矩阵为

$P^3 = \begin{bmatrix} 0.7 & 0.2 & 0.1 \\ 0.4 & 0.5 & 0.1 \\ 0.2 & 0.4 & 0.4 \\ \end{bmatrix}^3 \\ = \begin{bmatrix} 0.551 & 0.31 & 0.139 \\ 0.524 & 0.337 & 0.139 \\ 0.47 & 0.364 & 0.166 \\ \end{bmatrix}$

而根据题意, 初始时刻的概率分布 $ \alpha_0 = (0, 0, 1) $, 因此有

$\alpha_3 = \alpha_0 P^3 = \begin{pmatrix} 0.47 \\ 0.364 \\ 0.166 \\ \end{pmatrix}^T$

故自由党第三代子女加入工党的概率为0.364.

Extra

HMM (Hidden Markov Model, 隐式Markov模型): 参见一点简短的HMM笔记

References

¹. 百度百科词条动态规划 ↩

². 百度百科词条无后效性 ↩

³. 百度百科词条马尔可夫性质 ↩

⁴. 百度百科词条动态规划 ↩

⁵. pinard的博客园文章 MCMC(二)马尔科夫链 ↩

QUST Data Science Research Association

青岛科技大学数据科学研究协会