poster467

移动迷宫2:求期望

73011
2
本文将依次给出老鼠逃出迷宫所需时间的3种方法.
移动迷宫2:求期望
11 人挑战成功
返回挑战
challenge-problem-icon

完成本期挑战需要达到:

本科数学水平

11 / 35 读者挑战成功
题目

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

选项

跳过看答案

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

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

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

问题回顾

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

image

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

随机变量及其期望

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

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

状态转移矩阵的修正

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

但需要注意

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

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

image

故状态转移等式修正为

此时表示的即为经过次转移后老鼠第一次落在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又平均需要次转移.

image

故我们可以得到

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

于是得到线性方程组,

不难解得,.

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

其中显然有.

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

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

参考文献

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

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

  1. 用数值来表达随机试验结果的变量. 详见维基百科
  2. 随机变量取值的加权平均,权重为该取值的概率. 详见维基百科
  3. 事实上我们可以计算转移矩阵的次方,就能得到各元素关于的表达式. 其计算方法请参考任一本《线性代数》的教材.
  4. 对于分子分母极限都为零或都为无穷大时,可以分别求导再求极限. 详见维基百科
  5. 一种借助计算机生成随机数来进行多次实验,根据结果统计来估计理论值的方法, 详见维基百科
1

发布于1 年前
慕容玖
level4
展开所有评论
发表评论
1

发布于1 年前
Aaron
level3
展开所有评论
发表评论