双urn交换球实验的期望完成轮数求解及通用方法咨询

嘿，这个问题属于吸收马尔可夫链的期望吸收时间问题，咱们一步步拆解，不仅能算出结果，还能搞懂这类多分支问题的通用解法：

首先，我们可以用第一个urn中的红球数量来定义状态（因为总红球数是4个，第二个urn的红球数就是4 - 第一个urn红球数，状态完全由这个数决定）：

• S₀：第一个urn 0红4蓝，第二个4红0蓝（和初始状态对称）
• S₁：第一个urn 1红3蓝，第二个3红1蓝（和S₃对称）
• S₂：第一个urn 2红2蓝，第二个2红2蓝（目标吸收态，到达后实验结束，期望时间为0）
• S₃：第一个urn 3红1蓝，第二个1红3蓝
• S₄：第一个urn 4红0蓝，第二个0红4蓝（初始状态）

因为对称性，E₀=E₄，E₁=E₃，我们只需要求解E₄（初始状态到目标的期望轮数）和E₃即可。

对于每个状态，期望轮数 = 当前1轮 + 后续各状态的期望轮数×转移概率：

1. 从S₄出发：
   第一个urn只能取出红球（概率1），第二个urn只能取出蓝球（概率1），交换后必然进入S₃。所以：

   E₄ = 1 + E₃
   

2. 从S₃出发：
   第一个urn有3红1蓝，第二个有1红3蓝，四种交换情况：

   • 取红（3/4）+ 取红（1/4）：交换后红球数不变，留在S₃，概率(3/4)(1/4)=3/16
   • 取红（3/4）+ 取蓝（3/4）：交换后第一个urn变成2红2蓝，到达目标S₂，概率(3/4)(3/4)=9/16
   • 取蓝（1/4）+ 取红（1/4）：交换后第一个urn变成4红0蓝，回到S₄，概率(1/4)(1/4)=1/16
   • 取蓝（1/4）+ 取蓝（3/4）：交换后红球数不变，留在S₃，概率(1/4)(3/4)=3/16

   所以期望方程为：

   E₃ = 1 + (3/16 + 3/16)E₃ + (1/16)E₄ + (9/16)×0
   

   简化后：

   E₃ = 1 + (6/16)E₃ + (1/16)E₄
   

把E₄ = 1 + E₃代入E₃的方程：

E₃ = 1 + (6/16)E₃ + (1/16)(1 + E₃)

展开并整理：

E₃ = 1 + 6E₃/16 + 1/16 + E₃/16
E₃ = 17/16 + 7E₃/16
16E₃ = 17 + 7E₃
9E₃ = 17 → E₃ = 17/9 ≈ 1.89

再代入E₄的表达式：

E₄ = 1 + 17/9 = 26/9 ≈ 2.89

所以初始状态到目标的期望轮数是26/9（约2.89轮）。

这类有多个状态转移分支的问题，核心思路是马尔可夫链的期望状态方程法：

• 定义清晰的状态：尽量用最少的变量覆盖所有可能情况，利用对称性减少变量数量（比如这里的S₁和S₃对称，直接合并为一个变量）
• 列出每个状态的转移概率：明确从当前状态到其他所有状态的概率
• 建立线性方程组：每个状态的期望轮数等于1（当前轮）加上后续各状态期望×对应概率，吸收态的期望为0
• 解线性方程组：可以用代入消元、矩阵消元等方法求解

对于这类对称的吸收马尔可夫链，有几个简化技巧：

1. 利用对称性减少变量：比如这里S₁和S₃、S₀和S₄对称，直接把对称状态的期望设为相等，减少方程组的变量数，大幅简化计算
2. 递推关系简化：如果状态可以按某种顺序排列（比如按红球数量从0到4），可以建立递推公式，避免复杂的矩阵运算
3. 鞅方法（进阶）：对于一些特殊结构的马尔可夫链，可以构造鞅，利用鞅的停时定理直接计算期望，但这个方法需要一定的随机过程基础，适合复杂场景

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