带‘碰撞’粒子的整数区间随机游走问题技术问询

首先咱们先把问题的核心规则再明确下，避免歧义：

考虑两个粒子$p_1$、$p_2$在整数集合$[0,n]$（即整数0, 1, …, n）上执行均匀随机游走，规则修改如下：每个时间步，$p_1$以相等概率随机选择向左或向右移动，尝试前往目标位置；若该位置已被$p_2$占据，则$p_1$保持不动。随后$p_2$针对$p_1$执行相同的移动流程。粒子初始位置分别为0和1，n为吸收状态。

接下来我从几个关键维度拆解这个问题：

1. 状态空间定义 #

我们可以用有序对$(x,y)$来表示系统的状态，其中$x$是$p_1$的位置，$y$是$p_2$的位置。根据规则，$x \neq y$（碰撞时粒子不会移动到对方位置，初始状态也是$0 \neq 1$），且$0 \leq x,y \leq n$。另外，当$x=n$或$y=n$时，系统进入吸收态（默认粒子到达n后不再移动，这是随机游走吸收态的常规设定）。

2. 状态转移细节 #

对于任意非吸收态$(x,y)$，每一步的转移分两个阶段：

• 第一阶段：$p_1$移动
  • 50%概率尝试左移：
    • 若$x=0$，左移无效，$p_1$位置不变；
    • 若$x>0$且$x-1 \neq y$，则$p_1$移动到$x-1$；
    • 若$x>0$且$x-1 = y$，$p_1$保持原位置。
  • 50%概率尝试右移：
    • 若$x=n$，右移无效（已处于吸收态）；
    • 若$x<n$且$x+1 \neq y$，则$p_1$移动到$x+1$；
    • 若$x<n$且$x+1 = y$，$p_1$保持原位置。
• 第二阶段：$p_2$移动
  逻辑和$p_1$完全一致，只是要基于$p_1$更新后的位置进行判断：
  • 50%概率尝试左移：
    • 若$y=0$，位置不变；
    • 若$y>0$且$y-1 \neq x_{\text{新}}$，则$p_2$移动到$y-1$；
    • 若$y>0$且$y-1 = x_{\text{新}}$，$p_2$保持原位置。
  • 50%概率尝试右移：
    • 若$y=n$，位置不变（已处于吸收态）；
    • 若$y<n$且$y+1 \neq x_{\text{新}}$，则$p_2$移动到$y+1$；
    • 若$y<n$且$y+1 = x_{\text{新}}$，$p_2$保持原位置。

3. 常见问题的解决思路 #

如果要计算某粒子先到达n的概率或者系统到达吸收态的期望步数，可以用马尔可夫链建模：

• 先枚举所有非吸收态，构建转移矩阵；
• 对于吸收概率问题：设$P(x,y)$为从状态$(x,y)$出发，$p_1$先到达n的概率，根据转移规则列出线性方程组求解；
• 对于期望步数问题：设$T(x,y)$为从状态$(x,y)$到达吸收态的期望步数，同样列方程组求解。

举个小例子，当$n=2$时，非吸收态有$(0,1)$、$(1,0)$、$(0,2)$（$p_2$已吸收）、$(2,1)$（$p_1$已吸收）。初始状态是$(0,1)$：
$p_1$尝试右移到1但被$p_2$占据，所以不动；随后$p_2$尝试右移到2（未被$p_1$占据），进入状态$(0,2)$。之后$p_1$每次有50%概率右移到1，再之后又有50%概率右移到2，通过简单递归就能算出$p_1$先到2的概率和期望步数。

4. 简化与模拟技巧 #

• 对称性简化：如果交换$p_1$和$p_2$的角色，调整初始条件，可以简化部分对称场景的计算；
• 数值模拟：当$n$较大时，用代码模拟大量游走过程是高效的方法。比如下面的Python核心模拟片段：

import random

def simulate_one_run(n):
    p1, p2 = 0, 1
    steps = 0
    while p1 != n and p2 != n:
        # p1移动逻辑
        move_p1 = random.choice([-1, 1])
        new_p1 = p1 + move_p1
        if 0 <= new_p1 <= n and new_p1 != p2:
            p1 = new_p1
        # p2移动逻辑
        move_p2 = random.choice([-1, 1])
        new_p2 = p2 + move_p2
        if 0 <= new_p2 <= n and new_p2 != p1:
            p2 = new_p2
        steps += 1
    return (p1 == n, steps)

# 模拟10000次统计结果
total_runs = 10000
p1_win_count = 0
total_steps_sum = 0
for _ in range(total_runs):
    win_flag, run_steps = simulate_one_run(5)
    if win_flag:
        p1_win_count += 1
    total_steps_sum += run_steps

print(f"p1先到达n的概率: {p1_win_count/total_runs:.4f}")
print(f"到达吸收态的平均步数: {total_steps_sum/total_runs:.2f}")

内容的提问来源于stack exchange，提问作者aellab