0339 佩雷迪尔
* * * *
拉格朗日计划
* * * *
佩雷迪尔

“他走向一座山谷,谷内小河淙淙,谷外绿树环绕,小河两岸,芳草萋萋。在河的一侧他看到一群白色的绵羊,在河的另一侧他看到一群黑色的绵羊,每当一只白色绵羊叫唤时,一只黑色绵羊便会穿过河流并变成白色,而每当一只黑色绵羊叫唤时,一只白色绵羊也会穿过河流并变成黑色。” ——来自威尔士民间故事

每只羊(无论颜色)都会等概率地成为下一只叫唤的羊,当一只羊穿过河流变色之后,佩雷迪尔都可以移除一定数量的白色绵羊,以最大化黑色绵羊最终数量的期望值。

记$E(n)$是两群羊初始时均为n只,且佩雷迪尔使用最优策略时黑色绵羊最终数目的期望值,例如$E(5)\approx6.871346$。

求$E(10000)$,结果保留6位小数。

注:原题的题面中遗漏了这样一条重要说明:该过程在所有的羊都变为黑色或都变为白色后会终止,否则本题以及题中佩雷迪尔的策略都没有任何意义。

本题难度:



解答

本题是概率论中的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}")