连载

标签

马尔可夫链入门

随机过程求概率

292

本文从一道老鼠版Maze Runer(移动迷宫)的趣味问题入手了解马尔可夫链随机过程.

完成本期挑战需要达到：

本科数学水平

10 名读者已经挑战成功

题目

如下图所示的迷宫共有5个房间, 相邻房间有门相通, 迷宫里有一只小老鼠，它以每分钟一格的速度在迷宫里乱窜，它通过各扇门的机会均等，并且每次都会移动到一个不同的房间. 那么小老鼠从3号房间出发5分钟后回到3号房间的概率是__________.

选项

$\text{[math]}$

2023年04月28日 08:00

有 0 人认为该挑战有问题

报告问题

在高中阶段, 矩阵和矩阵乘法的教学往往不被重视. 在绝大多数高中生眼里, 把一些数字排列成 $\text{[math]}$ 行 $\text{[math]}$ 列然后用圆括号括起来就是矩阵, 把矩阵静态的理解为一种存储数字的方式, 而把矩阵的运算看作是一种数字运算的批处理, 对矩阵乘法仅仅停留在规则记忆的层面上, 其应用情境也大多局限在表示线性方程组或诸如小明、小红、小王买铅笔、钢笔、圆珠笔的问题上. 那么今天我们将从一道老鼠版Maze Runer(移动迷宫)的趣味问题入手, 带你看一看矩阵的真正实力.

移动迷宫问题

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

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

把问题简化

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

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

那么, 老鼠经过一次移动, 1分钟后在1-4号的格子的概率分别为 $\text{[math]}$ 、 $\text{[math]}$ 、 $\text{[math]}$ 、 $\text{[math]}$ .

我们不妨用向量 $\text{[math]}$ 表示 $\text{[math]}$ 分钟后老鼠在1-4号的格子的概率, 故 $\text{[math]}$ .

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

考虑落在1号格子的情况, 其对应有两条路径, $\text{[math]}$ 和 $\text{[math]}$ .

那么根据老鼠每次的移动相互独立和加法原理, 我们得到老鼠落在1号格子的概率为 $\text{[math]}$ .

同理可得落在2号格子的概率也为 $\text{[math]}$ , 故 $\text{[math]}$ .

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

一般地, 不妨用 $\text{[math]}$ 表示 $\text{[math]}$ 分钟老鼠落在 $\text{[math]}$ 号格子的概率, 则有

$\text{[math]}$

更一般地, 我们可以用 $\text{[math]}$ 表示老鼠从 $\text{[math]}$ 号格子向 $\text{[math]}$ 号格子移动的概率, 那么

$\text{[math]}$

即

$\text{[math]}$

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

$\text{[math]}$

马尔可夫链

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

我们把经过 $\text{[math]}$ 次转移后处于各个状态的概率所组成的向量 $\text{[math]}$ 称为状态向量. $\text{[math]}$ 称为初始状态向量, 即

$\text{[math]}$ 其中 $\text{[math]}$ 表示经过 $\text{[math]}$ 次转移后处于状态 $\text{[math]}$ 的概率.

我们把各个状态之间转移的概率所组成的方阵 $\text{[math]}$ , 称为转移矩阵. 即 $\text{[math]}$ 其中 $\text{[math]}$ 是从状态 $\text{[math]}$ 转移到状态 $\text{[math]}$ 的概率[1].

注意这里第 $\text{[math]}$ 行第 $\text{[math]}$ 列的元素是从状态 $\text{[math]}$ 转移到状态 $\text{[math]}$ 的概率.

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

$\text{[math]}$

根据矩阵乘法的性质, 不难推得 $\text{[math]}$ .

简化版问题的矩阵解法

在上文简化版问题中,

$\text{[math]}$

故 $\text{[math]}$

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

#!/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 ]]

由上述结果, 我们看到, 老鼠在五分钟后逃出的概率为 $\text{[math]}$ . 如果老鼠的移动速度翻倍那无非就是移动的次数从5次变为10次, 得到逃出的概率为 $\text{[math]}$ .

进一步思考

若迷宫不会坍塌, 则老鼠平均需要经过几分钟才能逃出迷宫？
若老鼠在进行足够多（无穷多）次移动后, 是不是一定会逃出迷宫？
若迷宫并不存在出口, 则老鼠在进行足够多（无穷多）次移动后, 落在各个格子里的概率如何？

参考文献

[1] David C. Lay & Steven R. Lay & Judi J. McDonald. Linear Algebra and Its Applications. Pearson Higher Ed.

本文最早于2018年12月发布于橘子数学公众号.