0151 纸张大小期望
* * * *
拉格朗日计划
* * * *
纸张大小期望

一家打印店每周有16份打印工作,每份打印工作需要一张A5大小的纸。

每周一早晨,工作人员会打开一个新信封,信封中有一张A1大小的纸。

他将这张纸一裁为二,得到两张A2大小的纸。再将其中一张一裁为二,得到两张A3大小的纸,如此直到裁出一张用于第一份打印工作的A5大小的纸,其它剩余的纸张会被重新放回信封里。



接下来的每次打印工作前,工作人员都会从信封里随机拿出一张纸,如果这张纸恰好是A5大小,则他会直接拿去使用,否则他会重复一裁为二的过程直到得到一张A5大小的纸,并将剩下的纸重新放回信封里。

除了每周的第一次工作必定需要裁剪和最后一次工作无需裁剪外,求一周中当工作人员拿纸时发现信封里恰好只有一张纸的次数的期望值。答案应当保留六位小数,即以x.xxxxxx的形式给出。

本题难度:



解答

容易想到的方法是做许多次模拟并统计频次,不过由于题中要求六位精度,而多组一百万次实验都没有达到足够的精度,因此推测模拟的收敛速度比较慢,需要找到其他的方法。

事实上本题的解析解可以递归计算。令a、b、c、d分别为信封中A2、A3、A4、A5纸的数量。令$f(a,b,c,d)$为从状态a、b、c、d开始,此后信封中恰好只有一张纸的次数的期望值,如此则有 $$f(0,0,0,0)=0$$ 以及 \begin{align*} f(a,b,c,d)=&f(a-1,b+1,c+1,d+1)\cdot\frac{a}{a+b+c+d} \\ &+f(a,b-1,c+1,d+1)\cdot\frac{b}{a+b+c+d} \\ &+f(a,b,c-1,d+1)\cdot\frac{c}{a+b+c+d} \\ &+f(a,b,c,d-1)\cdot\frac{d}{a+b+c+d} \\ &+\begin{cases}1 & a+b+c+d=1 \\ 0 & a+b+c+d>1\end{cases} \end{align*} 结果是$f(1,1,1,1)-1$ (需要排除最后一轮,因此减1),约为$0.464399$。

def f(a,b,c,d):
  if a+b+c+d==0:
      return 0
  else:
      h=1.0*f(a-1,b+1,c+1,d+1)*a/(a+b+c+d) if a>0 else 0
      i=1.0*f(a,b-1,c+1,d+1)*b/(a+b+c+d) if b>0 else 0
      j=1.0*f(a,b,c-1,d+1)*c/(a+b+c+d) if c>0 else 0
      k=1.0*f(a,b,c,d-1)*d/(a+b+c+d) if d>0 else 0
      return h+i+j+k+(a+b+c+d==1)

print "%.6f" %(f(1,1,1,1)-1)