马尔可夫链模型是什么？

Question

马尔可夫

马尔可夫链模型是什么？

可以通俗易懂、详细具体地解释一下吗？谢谢。

关注者

552

被浏览

429,632

26 个回答

以下内容节选自我的博客《从马尔可夫链看矩阵的乘法》，从一道具体的老鼠版Maze Runner问题入手理解马尔可夫链与矩阵乘法，原文是写给中学生看的，所以应该还算通俗. 欢迎关注微信公众号：橘子数学 获得更多适合高中生的数学原创文章.

问题

如下图所示的迷宫共有9个格子，相邻格子有门相通，9号格子就是迷宫出口. 整个迷宫将会在5分钟后坍塌. 1号格子有一只老鼠，这只老鼠以每分钟一格的速度在迷宫里乱窜（它通过各扇门的机会均等）。求此老鼠在迷宫坍塌之前逃生的概率。如果这只老鼠速度提高一倍，则老鼠在迷宫坍塌之前逃生的概率能增加多少？

以上是2018年上海应用数学知识竞赛的一道初赛试题，橘子老君将会讲解如何用矩阵乘法来解决这个问题.

简化版问题

首先，我们不妨先把问题简化为一个4个格子的迷宫，老鼠仍以每分钟一格的速度在迷宫里乱窜，4号格子是迷宫的出口.

由通过各扇门的机会均等，可得格子之间转移的概率如图（由于4号格子是出口，所以老鼠到达四号格子后不会向其他格子转移），

那么，老鼠经过一次移动，1分钟后在1-4号的格子的概率分别为 0 、 0.5 、 0.5 、 0 .

我们不妨用向量 v_n 表示 n 分钟后老鼠在1-4号的格子的概率，故 v_1=\left(0,0.5,0.5,0\right) .

如上图，通过列举每一条路径，当老鼠经过两次移动，我们发现老鼠可能落在1号或4号格子.

考虑落在1号格子的情况，其对应有两条路径， 1\rightarrow2\rightarrow1 和 1\rightarrow3\rightarrow1 .

那么根据老鼠每次的移动相互独立和加法原理，我们得到老鼠落在1号格子的概率为 0.5\times0.5+0.5\times0.5=0.5 .

同理可得落在2号格子的概率也为 0.5 ，故 v_2=\left(0.5,0,0,0.5\right) .

如上图，进一步列举3分钟后的每一条路径，考虑落在3号的格子的情况，对应的路径有两条 1\rightarrow2\rightarrow1\rightarrow3 和 1\rightarrow3\rightarrow1\rightarrow3 . 通过分析格子间的转移概率不难得到，要使老鼠3分钟后落在3号格子，则2分钟后老鼠必须在1号格子. 故我们接下来将尝试写出相邻两分钟在不同格子概率的递推关系.

一般地，不妨用 v_n^{(i)} 表示 n 分钟老鼠落在 i 号格子的概率，则有

由以上递推关系，我们可以通过编程由计算机来完成计算：

#!/usr/bin/env python3

n = 5  # 计算到n分钟后的情况
v = (1, 0, 0, 0)  # 0分钟后的情况
i = 0  # 当前计算到i分钟后
while i < n:
    v = (
        0.5 * v[1] + 0.5 * v[2],
        0.5 * v[0],
        0.5 * v[0],
        0.5 * v[1] + 0.5 * v[2] + v[3]
    )
    i = i + 1
    print('v' + str(i) + ': ' + str(v))

Output:

v1: (0.0, 0.5, 0.5, 0.0)
v2: (0.5, 0.0, 0.0, 0.5)
v3: (0.0, 0.25, 0.25, 0.5)
v4: (0.25, 0.0, 0.0, 0.75)
v5: (0.0, 0.125, 0.125, 0.75)

由上述结果，我们看到，老鼠在五分钟后逃出的概率为 0.75 . 如果老鼠的移动速度翻倍那无非就是移动的次数从5次变为10次，得到逃出的概率为 0.96875 .

更一般地，我们可以用 a_{ij} 表示老鼠从 i 号格子向 j 号格子移动的概率，那么

即

故由矩阵乘法的定义，递推关系式可以写成：

马尔可夫链：一些定义

至此我们得到了解决此问题的矩阵形式,我们把此类在不同状态间随机移动的数学模型称为马尔可夫链. 老鼠在随机移动的过程中可能落在4个格子内，即存在4个状态. 而每做一次移动，其状态即发生转移. 为了讨论更一般的情况，我们不妨设有 m 种状态.

我们把经过 n 次转移后处于各个状态的概率所组成的向量 \mathrm{x}_n 称为状态向量. \mathrm{x}_0 称为初始状态向量，即

其中 a_j 表示经过 n 次转移后处于状态 j 的概率.

我们把各个状态之间转移的概率所组成的方阵 P ，称为转移矩阵. 即

其中 p_{ij} 是从状态 j 转移到状态 i 的概率[^1].

[^1]: 注意这里第 i 行第 j 列的元素是从状态 j 转移到状态 i 的概率.

那么同上文中的推导，我们可以得到相邻两个状态向量的关系，

根据矩阵乘法的性质，不难推得 \mathrm{x_{n}}=P^n \mathrm{x_0} .

简化版问题的矩阵解法

在上文简化版问题中，

故

下面我们用计算机来完成矩阵乘法计算：

#!/usr/bin/env python3

import numpy as np
n = 5  # 计算到n次转移后的情况
i = 0  # 当前进行到i次转移
x = np.array([
    [1],
    [0],
    [0],
    [0]])  # 当前的状态向量
P = np.array([
    [0, 0.5, 0.5, 0],
    [0.5, 0, 0, 0],
    [0.5, 0, 0, 0],
    [0, 0.5, 0.5, 1]
])  # 转移矩阵
while i < n:
    x = P.dot(x)  # x=P*x
    i = i+1
    print('x'+str(i)+': \n'+str(x))

Output:

x1: 
[[0. ]
 [0.5]
 [0.5]
 [0. ]]
x2: 
[[0.5]
 [0. ]
 [0. ]
 [0.5]]
x3: 
[[0.  ]
 [0.25]
 [0.25]
 [0.5 ]]
x4: 
[[0.25]
 [0.  ]
 [0.  ]
 [0.75]]
x5: 
[[0.   ]
 [0.125]
 [0.125]
 [0.75 ]]