同一骨架 2011 年河南预赛 第 7 题 · P009855
运动路径很多时,两题都先只记录与目标有关的位置类别。只有同类位置到各目标类别的转移概率一致,才能合并状态,再利用对称关系降低递推规模。
两只兔子的相对位置与一只小虫是否在原顶点,看起来不同,却都在寻找足够而尽量少的状态信息。
正八边形上两只独立随机游走兔子的相遇期望
设多边形 为一个正八边形,有 只兔子最初分别位于顶点 和 处。每过 分钟, 只兔子同时随机、独立地跳到与其当前位置相邻 的两个顶点中的一个。一旦 只兔子跳到了同一个顶点,则停止跳跃。则当兔子停止跳跃时, 跳跃时间的分钟数的期望是。
分数写 a/b,根号写 √ 或 sqrt,π 写 pi 也可以。
只记录两只兔子的相对位置。
先回想这道题的想法,再试试当前题。
它们初始相隔四条边,而且相对位移每次只改变 或 ,所以缩小一半后成为四个状态上的带停留随机游走。
给八个顶点按模 编号。设两只兔子位置编号之差除以 后,在模 意义下为状态 。两只兔子每次分别向顺、逆时针跳一步,因此相对状态
的概率分别为
状态 表示相遇。初始两点 相隔四条边,故初始状态为 。
记从状态 到首次相遇的期望时间分别为 。由对称性,
令 。作一步分析得到
即
解得
所以从初始状态 出发的期望停止时间为
分钟。
两只兔子同时反向跳会交换相对状态的相邻方向,同时同向跳使相对状态不变,三种概率 确为 。初始距离为偶数,过程始终保持偶数距离,因此四状态模型没有漏掉 可达状态。
多个独立随机游走的相遇时间,通常先转成一个相对位置的随机游走。对有限状态逐状态作 一步条件期望,即可得到线性方程组。
把两个兔子的绝对位置压成差除以2的四状态环,再利用对称只列两个期望方程,需计入同向跳的原地等待概率。
同一骨架 2011 年河南预赛 第 7 题 · P009855
运动路径很多时,两题都先只记录与目标有关的位置类别。只有同类位置到各目标类别的转移概率一致,才能合并状态,再利用对称关系降低递推规模。
两只兔子的相对位置与一只小虫是否在原顶点,看起来不同,却都在寻找足够而尽量少的状态信息。
易混 2025 年云南预赛 · P006404
展开中每个选项可看作一次步长选择,常数项只要求固定次数后的净位移为零;相遇停止的随机游走还约束路径何时首次命中,不能只看最后的位置。后者需把首次到达的过程信息保留在状态里。
前题是无中途限制的有限选择计数,后题的环状相对位置、停留权重与首次停止共同决定期望;终点系数不能直接替代停止时间递推。
已记下,谢谢!