本题是概率论中的Mabinogion sheep问题,详细的讨论比较复杂,以下仅作启发式的说明:
设$E(b,w)$是有b只黑羊和w只白羊时的最终期望,那么
$$E(b,w)=\frac{w}{w+b}E(b+1,w-1)+\frac{b}{w+b}E(b-1,w+1),$$<
若改变右侧的$E(b+1,w-1)$为$E(b+1,w_1)$以及$E(b-1,w+1)$为$E(b+1,w_2)$后可以使之增加($w_1 < w-1$且$w_2 < w+1$),那么就应该尝试移除白羊。
让我们以$b=2, w=1$的简单情况为例来尝试说明变化过程,此时有
$$E(2,1)=\frac{1}{3}\times 3+\frac{2}{3}E(1,2),$$
即有$1/3$的机会唯一的白羊变为黑羊直接结束,$2/3$的机会转化为另一种状态。同理
$$E(1,2)=\frac{1}{3}\times 0+\frac{2}{3}E(2,1),$$
两式联立可以解得$E(2,1)=9/5$以及$E(2,1)=6/5$。若改变上式子右侧的E$(2,1)$为$E(2,0)$,也就是在白羊变黑后立即移除另一只唯一的白羊,就可以把$E(2,1)$提升到$4/3$,从而进一步提高$E(2,1)$。
由对称性经过尝试可以验证这样一个策略:始终保持黑羊对白羊的优势。亦即若变化后若白羊的数量多于黑羊,就其移除使之数量变为$b-1$。
由此递推即可得结果$19823.542204$。
注:为便于作除法,以下代码为Python 3。
target=20000
e=[0]*(target//2+2)
n=1
while n < target+1:
p=1
for j in range(n-1,n//2,-1):
p=1+p*(n/j-1)
p=1/p
e[n//2+1]=p*n+(1-p)*e[n//2]
n+=2 if n < target-1 else 1
print(f"{0.5*e[target//2-1]+0.5*e[target//2+1]:.6f}")
|