移动迷宫：探秘马尔可夫链

在高中阶段, 矩阵和矩阵乘法的教学往往不被重视. 在绝大多数高中生眼里, 矩阵只是一种静态的存储数字的方式, 矩阵的运算也只是一种数字运算的批处理, 比如我们的高中生对矩阵乘法仅仅停留在规则记忆的层面上, 对矩阵的应用情境也大多局限在表示线性方程组或诸如小明、小红、小王买铅笔、钢笔、圆珠笔的问题上.

那么本文我们就从一道老鼠版移动迷宫(Maze Runer ^[1])的趣味问题入手, 通过建立矩阵模型, 并用矩阵乘法对模型进行求解从而解决问题. 而在此过程中, 自然的引入马尔可夫链随机过程的基本概念和求概率的基本方法.

移动迷宫问题

如下图所示的迷宫共有4个格子, 相邻格子有门相通, 4号格子就是迷宫出口. 1号格子有一只老鼠, 这只老鼠以每分钟一格的速度在迷宫里乱窜（它通过各扇门的机会均等）.

以上是2018年上海应用数学知识竞赛的一道初赛试题改编版, 原题是迷宫有9个格子, 9号格子是迷宫出口. 改编版只是将迷宫大小做了一个简化, 其他条件不变.

接下来我们通过问题分析引出递推关系, 建立矩阵模型并借助矩阵乘法运算从而顺利的解决这个移动迷宫问题. 在建立矩阵模型的同时, 我们将介绍马尔可夫链的相关概念.

问题分析

根据题意, 老鼠通过各扇门的机会均等, 由此可直接写出格子之间转移的概率, 如图所示：

注：由于4号格子是出口, 所以老鼠到达四号格子后不会向其他格子转移.

接下来我们依次来计算老鼠经过几次移动后落在每个格子的概率.

移动一次

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

我们不妨用向量表示分钟后老鼠在1-4号格子的概率, 故.

移动两次

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

考虑落在1号格子的情况, 其对应有两条路径, 和.

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

同理可得落在4号格子的概率也为.

故.

移动三次

如图, 进一步列举3分钟后即老鼠移动三次后的的每一条路径.

考虑落在3号的格子的情况, 对应的路径有两条和. 通过分析格子间的转移概率不难得到, 要使老鼠3分钟后落在3号格子, 则2分钟后老鼠必须在1号格子.

故我们接下来将尝试写出相邻两分钟在不同格子概率的递推关系.

一般地, 不妨用 表示分钟后老鼠落在号格子的概率, 则有

矩阵模型

更一般地, 我们可以用表示老鼠从号格子向号格子移动的概率, 那么

即

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

马尔可夫链

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

我们把经过次转移后处于各个状态的概率所组成的向量 称为状态向量. 称为初始状态向量, 即

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

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

其中 是从状态 转移到状态 的概率 ^[2].

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

根据矩阵乘法的性质, 不难推得

矩阵模型求解

回到老鼠移动迷宫问题,

故

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

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

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

进一步思考

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

参考文献

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

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

1. "Maze Runner" 是一部以詹姆斯·达什纳(James Dashner)的同名小说为基础的系列电影的名字, 中文翻译为"移动迷宫". ⬅
2. 注意这里第 行第 列的元素是从状态 转移到状态 的概率. ⬅