若迷宫不会坍塌,则老鼠平均需要经过几分钟才能逃出迷宫?
完成本期挑战需要达到:
本科数学水平
一枚硬币, 抛出正面和反面的概率都是
在《移动迷宫:探秘马尔可夫链》一文中,我们通过一道老鼠在迷宫中随机游走的问题介绍了马尔可夫链,从而更好地理解了矩阵和矩阵的乘法. 本文将解决文末留下的第一个问题:
我们首先从期望的定义出发,把问题转化为一个无穷数列求和的问题,并用统计模拟方法验证结果. 而后我们给出一个更简洁的方法,把问题转化为一个线性方程组求解的问题.
如下图所示的迷宫共有4个格子, 相邻格子有门相通, 4号格子就是迷宫出口. 1号格子有一只老鼠, 这只老鼠以每分钟一格的速度在迷宫里乱窜(它通过各扇门的机会均等).
例 1 ( 移动迷宫 )
若迷宫不会坍塌,则老鼠平均需要经过几分钟才能逃出迷宫?
用
根据题意, 老鼠每分钟转移一次, 所以要求经过几分钟才能逃出迷宫, 我们需要关注的是老鼠到达4号格子(出口)所需的平均转移次数,故把到达4号格子所需的转移次数看作随机变量
而根据随机变量期望的定义可得,
但需要注意
因为
为了方便,我们不妨新增一个状态5(已逃出),如图落在状态4(4号格子)及状态5的老鼠,经过一次转移后
故状态转移等式修正为
此时
为了求出
#!/usr/bin/env python3
import numpy as np
n = 15 # 计算到n次转移后的情况
i = 0 # 当前进行到i次转移
x = np.array([
[1],
[0],
[0],
[0],
[0]]) # 当前的状态向量
P = np.array([
[0, 0.5, 0.5, 0, 0],
[0.5, 0, 0, 0, 0],
[0.5, 0, 0, 0, 0],
[0, 0.5, 0.5, 0, 0],
[0, 0, 0, 1, 1]
]) # 转移矩阵
while i < n:
x = P.dot(x) # x=P*x
i = i+1
print('P(x='+str(i)+'): '+str(x[3])) # 输出P(x=i)\
计算结果如下:
P(x=1): [0.]
P(x=2): [0.5]
P(x=3): [0.]
P(x=4): [0.25]
P(x=5): [0.]
P(x=6): [0.125]
P(x=7): [0.]
P(x=8): [0.0625]
P(x=9): [0.]
P(x=10): [0.03125]
P(x=11): [0.]
P(x=12): [0.015625]
P(x=13): [0.]
P(x=14): [0.0078125]
P(x=15): [0.]
通过观察
[3]我们发现,奇数次到达4号格子的概率为
没错就是高中数列求和的常见题型,一个等差数列一个等比数列分别相乘再相加,用错位相减法进行求和即可.
两式相减得,
解得
如果你学习过微积分,那么由洛必达法则
[4],我们可以得到
如果你没有学习过微积分,那么也很容易理解
因此
下面我们利用蒙特卡罗统计模拟法 [5],来检验我们得到的结果.
我们对以下程序进行了10万次实验模拟,其中每次实验都是从状态1出发,进行若干次随机转移直到到达状态4结束. 最终通过对实验结果记录的统计,得到平均转移次数.
#!/usr/bin/env python3
import numpy as np
from random import choices
from statistics import mean
class State(object):
def __init__(self,state_id):
self.transition_matrix = np.array([
[0, 0.5, 0.5, 0],
[0.5, 0, 0, 0],
[0.5, 0, 0, 0],
[0, 0.5, 0.5, 1],
]) # 转移矩阵
self.state_id = state_id # 状态ID: 状态1的ID为0
def move(self):
candidates = range(0, 4) # 转移目标
weights = self.transition_matrix[:, self.state_id] # 转移概率
result = choices(candidates, weights) # 产生随机转移结果
return State(result[0])
if __name__ == '__main__':
e = 100000 # 试验次数
r = [] # 试验结果
for i in range(0,e):
cur_state = State(0) # 初始状态: 状态1
count = 0 # 转移次数
while cur_state.state_id != 3:
cur_state = cur_state.move()
count += 1
r.append(count) # 记录结果
print(mean(r)) # 输出均值
所得结果如下,
4.0062
在这个问题中,我们要求的就是从状态1到状态4所需要的平均转移次数.
那我们不妨设
如图以
故我们可以得到
这里
于是得到线性方程组,
不难解得,
一般地,我们设
其中显然有
所得线性方程组的矩阵形式为
而一般的线性方程组的求解方法,这里就不具体展开了,有兴趣的读者可以在任一本线性代数的教材中找到相关内容.
[1] David C. Lay & Steven R. Lay & Judi J. McDonald. Linear Algebra and Its Applications. Pearson Higher Ed.
本文最早于2018年12月发布于橘子数学公众号.