五人圆桌传球场景下双球同持状态期望回合数求解求助

嗨，我来帮你梳理这个问题的解法～你已经精准抓住了状态转移的核心，接下来我们用期望递推法就能快速算出目标期望，不用非得先求$d_k$的完整分布哦，具体步骤如下：

第一步：定义状态期望 #

我们先给不同距离状态定义对应的期望回合数：

• $E_1$：当两球距离$d_k=1$时，到两球重合（$d=0$）所需的期望回合数
• $E_2$：当$d_k=2$时的期望回合数
• $E_3$：当$d_k=3$时的期望回合数

注意五人圆桌的对称性：距离3其实等价于反向的距离2，所以$E_3 = E_2$，这个结论能帮我们简化计算。

第二步：根据状态转移列递推方程 #

结合你已经观察到的转移概率，我们可以列出每个状态的递推关系：

1. 对于$E_1$：
   当前处于$d=1$时，下一回合有$\frac{3}{4}$概率保持$d=1$，$\frac{1}{4}$概率变成$d=2$，每一步都会消耗1个回合，因此：
   $$E_1 = 1 + \frac{3}{4}E_1 + \frac{1}{4}E_2$$
2. 对于$E_2$：
   当前处于$d=2$时，下一回合有$\frac{1}{2}$概率保持$d=2$，$\frac{1}{4}$概率直接到达终止状态$d=0$（此时不需要额外回合），$\frac{1}{4}$概率变成$d=3$（等价于$d=2$，对应期望$E_3=E_2$），因此：
   $$E_2 = 1 + \frac{1}{2}E_2 + \frac{1}{4} \times 0 + \frac{1}{4}E_2$$

第三步：解方程求期望 #

先解$E_2$的方程：
$$E_2 = 1 + \frac{1}{2}E_2 + \frac{1}{4}E_2$$
整理得：
$$E_2 - \frac{3}{4}E_2 = 1 \implies \frac{1}{4}E_2 = 1 \implies E_2 = 4$$

再把$E_2=4$代入$E_1$的方程：
$$E_1 = 1 + \frac{3}{4}E_1 + \frac{1}{4} \times 4$$
整理得：
$$E_1 - \frac{3}{4}E_1 = 2 \implies \frac{1}{4}E_1 = 2 \implies E_1 = 8$$

结论 #

初始状态下两球距离为1，要等到一个人持有两个球的期望回合数是8。

如果之后你确实需要求$d_k$的分布，可以用马尔可夫链的状态转移矩阵来计算n步后的状态概率，但对于求期望这个目标，递推法显然更高效。

备注：内容来源于stack exchange，提问作者Atmos