移动迷宫2：求期望

在《移动迷宫：探秘马尔可夫链》一文中，我们通过一道老鼠在迷宫中随机游走的问题介绍了马尔可夫链，从而更好地理解了矩阵和矩阵的乘法. 本文将解决文末留下的第一个问题：

• 若迷宫不会坍塌，则老鼠平均需要经过几分钟才能逃出迷宫？

我们首先从期望的定义出发，把问题转化为一个无穷数列求和的问题，并用统计模拟方法验证结果. 而后我们给出一个更简洁的方法，把问题转化为一个线性方程组求解的问题.

问题回顾

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

用表示经过次转移后的状态向量(处于各个状态的概率所组成的向量)，之前我们得到

随机变量及其期望

根据题意, 老鼠每分钟转移一次, 所以要求经过几分钟才能逃出迷宫, 我们需要关注的是老鼠到达4号格子(出口)所需的平均转移次数，故把到达4号格子所需的转移次数看作随机变量 ^[1]，即求随机变量的期望 ^[2].

而根据随机变量期望的定义可得，

状态转移矩阵的修正

表示的是经过次转移，老鼠落在4号格子(已逃出)的概率.

但需要注意

因为累计计算了前次转移到达4号格子的概率.

为了方便，我们不妨新增一个状态5（已逃出），如图落在状态4（4号格子）及状态5的老鼠，经过一次转移后落在状态5.

故状态转移等式修正为

此时表示的即为经过次转移后老鼠第一次落在4号格子的概率.

无穷数列的求和

为了求出, 根据修正后的状态转移矩阵, 如下修改之前的程序.

#!/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号格子的概率成等比数列，故

没错就是高中数列求和的常见题型，一个等差数列一个等比数列分别相乘再相加，用错位相减法进行求和即可.

两式相减得，

解得.

如果你学习过微积分，那么由洛必达法则 ^[4]，我们可以得到.

如果你没有学习过微积分，那么也很容易理解. 虽然当时，有和都趋于，但的增长趋势要远大于.

因此，即. 也就是平均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所需要的平均转移次数.

那我们不妨设表示从状态到状态4的平均转移次数，表示从状态转移到状态的概率. 则有

如图以为例，要考虑状态1到状态4的转移次数期望，先考虑从状态1出发的第一次转移, 其有0.5的概率到达状态2，有0.5的概率到达状态3. 而从状态2、3到达状态4又平均需要次转移.

故我们可以得到

这里是因为从状态1出发到达状态2、3耗费了一次转移.

于是得到线性方程组，

不难解得，.

一般地，我们设是状态到状态的转移次数期望， 则有

其中显然有.

所得线性方程组的矩阵形式为

而一般的线性方程组的求解方法，这里就不具体展开了，有兴趣的读者可以在任一本线性代数的教材中找到相关内容.

1. 用数值来表达随机试验结果的变量. 详见维基百科 ⬅
2. 随机变量取值的加权平均，权重为该取值的概率. 详见维基百科 ⬅
3. 事实上我们可以计算转移矩阵的次方，就能得到各元素关于的表达式. 其计算方法请参考任一本《线性代数》的教材. ⬅
4. 对于分子分母极限都为零或都为无穷大时，可以分别求导再求极限. 详见维基百科 ⬅
5. 一种借助计算机生成随机数来进行多次实验，根据结果统计来估计理论值的方法, 详见维基百科 ⬅
6. David C. Lay & Steven R. Lay & Judi J. McDonald. Linear Algebra and Its Applications. Pearson Higher Ed.
7. 本文最早于2018年12月发布于橘子数学公众号.