探索

话题

连载

标签

马尔可夫链入门

随机过程求期望

286

本文将依次给出老鼠逃出迷宫所需时间的3种方法.

完成本期挑战需要达到：

本科数学水平

9 名读者已经挑战成功

题目

一枚硬币, 抛出正面和反面的概率都是 $\text{[math]}$ , 现在连续抛这枚硬币, 直到出现连续3次正面朝上为止，那么平均要抛__________次.

选项

$\text{[math]}$

2023年05月10日 08:00

有 0 人认为该挑战有问题

报告问题

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

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

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

问题回顾

仍以4格问题为例，老鼠目前在1号格子，以每分钟一格的速度在迷宫里乱窜，4号格子是迷宫的出口，若迷宫不会坍塌，则老鼠平均需要经过几分钟才能逃出迷宫？

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

$\text{[math]}$

随机变量及其期望

我们关注的是老鼠到达4号格子(出口)所需的平均转移次数，故把到达4号格子所需的转移次数看作随机变量 $\text{[math]}$ [1]，即求随机变量 $\text{[math]}$ 的期望 $\text{[math]}$ [2].

用数值来表达随机试验结果的变量. 详见维基百科 ↩
随机变量取值的加权平均，权重为该取值的概率. 详见维基百科 ↩

而根据随机变量期望的定义可得， $\text{[math]}$

状态转移矩阵的修正

$\text{[math]}$ 表示的是经过 $\text{[math]}$ 次转移，老鼠落在4号格子(已逃出)的概率.

但需要注意 $\text{[math]}$ 因为 $\text{[math]}$ 累计计算了前 $\text{[math]}$ 次转移到达4号格子的概率.

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

故状态转移等式修正为 $\text{[math]}$

此时 $\text{[math]}$ 表示的即经过 $\text{[math]}$ 次转移后老鼠第一次落在4号格子的概率，即 $\text{[math]}$ .

无穷数列的求和

#!/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号格子的概率为 $\text{[math]}$ ，偶数次到达4号格子的概率成等比数列，故 $\text{[math]}$

事实上我们可以计算转移矩阵的 $\text{[math]}$ 次方，即得到各元素关于 $\text{[math]}$ 的表达式. 其计算方法请参考任一本《线性代数》的教材.

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

$\text{[math]}$

两式相减得，

$\text{[math]}$

解得 $\text{[math]}$ .

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

对于分子分母极限都为零或都为无穷大时，可以分别求导再求极限. 详见维基百科

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

因此 $\text{[math]}$ ，即 $\text{[math]}$ . 即平均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所需要的平均转移次数.

那我们不妨设 $\text{[math]}$ 表示从状态 $\text{[math]}$ 到状态4的平均转移次数， $\text{[math]}$ 表示从状态 $\text{[math]}$ 转移到状态 $\text{[math]}$ 的概率. 则有 $\text{[math]}$

如图以 $\text{[math]}$ 为例，要考虑状态1到状态4的转移次数期望，不妨先考虑从状态1出发的第一次转移. 其有0.5的概率到达状态2，有0.5的概率到达状态3，而从状态2、3到达状态4又平均需要 $\text{[math]}$ 次转移，故我们可以得到 $\text{[math]}$ 这里+1是因为从状态1出发到达状态2、3耗费了一次转移.