概率计算问题

mathe

还是挺复杂的。但是这个公式的好处是可以同时计算出P(n)的上界和下界。
我们可以先将求和公式里面每项进行变换，转化为
$2^{-(2n+1)}/{(1-(1-2^{-n})x)^2(1-(1-2^{-(n+1)})x)}$
我们记$b=2^{-(n+1)}$,上面项可以写成
${2b^2}/{(1-(1-2b)x)^2(1-(1-b)x)}$
=$2b^2*(1+2(1-2b)x+3(1-2b)^2x^2+4(1-2b)^3x^3+....)(1+(1-b)x+(1-b)^2x^2+(1-b)^3x^3+...)$
上面表达式中$x^m$的系数为
$2b^2*((1-b)^m+2*(1-2b)*(1-b)^{m-1}+....+(m+1)(1-2b)^m)$
如果记$t={1-2b}/{1-b}$,那么上面系数变为
$2b^2*(1-b)^m*(1+2t+3t^2+...+(m+1)t^m)$
$={2b^2*(1-b)^m*(1-(m+2)t^(m+1)+(m+1)t^(m+2))}/{(1-t)^2}$

mathe

于是如果对于一个给定的m,要计算P(m+2),我们需要对于所有的整数n,计算
i) $b_n=2^{-(n+1)}$,注意这里$b_n$非常小，而且收敛非常快
ii)$t_n={1-2b_n}/{1-b_n}$
iii)$s_n={2b_n^2*(1-b_n)^m*(1-(m+2)t_n^(m+1)+(m+1)t_n^(m+2))}/{(1-t_n)^2}$
然后对所有的$s_n$求和就可以了。

mathe

上面计算的收敛速度将会很快，唯一问题在于$t_n$太接近1了，直接计算$s_n$将会有很大的误差，所以我们最好能够将这一步进行一次转化
如果我们记$h_n=1-t_n=b_n/{1-b_n}$
那么
$s_n=2b_n^2*(1-b_n)^m*\sum_{k=0}^{m}(k+1)C_{m+2}^{k+2}(- h_n)^k$

最后得
$P(m+2)=\sum_{n=0}^{+infty} 2^{-(2n+2)}(1-2^{-(n+1)})^m\sum_{k=0}^{m}{(k+1)C_{m+2}^{k+2}}/{(1-2^(n+1))^k}$
               $=\sum_{n=0}^{+infty} 2^{-(n+1)(m+2)}\sum_{k=0}^{m}(k+1)C_{m+2}^{k+2}(-1)^k(2^(n+1)-1)^(m-k)$

mathe

上面求和过程中通常我们只能计算有限项$s_n$,而求和的结果自然只是一个下界。那么我们再看看能否再给出一个上界。
看11楼中$x^m$的系数为
$2b_n^2*((1-b_n)^m+2*(1-2b_n)*(1-b_n)^{m-1}+....+(m+1)(1-2b_n)^m)$
$<2b_n^2*(1+2+...+(m+1)$
$<b_n^2*(m+2)(m+1)$
所以如果我们直计算到第n项，那么余下的项之和不超过
$<(m+1)(m+2)sum_{k=n+1}^{+infty}b_n^2$
$=4/3(m+1)(m+2)4^{-(n+1)}$

mathe

由此我们可以看出，每多计算一项，计算精度将可以提高两个bit位。
再指定精度的情况下，我们可以非常容易的计算出需要计算多少项。

无心人

也就是你
拿着复杂当游戏
做不来

mathe

呵呵，计算中也有乐趣的。
不过上面的表达式还是无法得出P(m)极限是否存在
不过直接使用上面的公式计算P(m)到第一千项倒是没有问题，只是到1030项式，浮点溢出了（组合数太大了）
这些计算结果同通过递推公式的结果比较，可以看出它们是完全匹配的。所以这个公式是没有问题了。
只是这个公式用来求极限还是不行

gxqcn

佩服 mathe，把问题可以分析得如此透彻！
从公式推导，到程序设计，从整型到浮点，全部通吃。。。

浮点计算比较麻烦的地方是进行误差分析，且实现起来有很多讲究，
所以即便 GMP 也没有全部实现。

mathe

发现最后还可以进行一次，从而消除无穷求和项，结果变为
$\sum_{k=0}^{m}C_{m+2}^{k+2}(k+1)\sum_{j=0}^{m-k} C_{m-k}^j(-1)^{m-j} \frac{2^{-m-2+j}}{1-2^{-m-2+j}}$
$=\sum_{j=0}^{m} C_{m+2}^{j} (-1)^{m-j} (1+(m-j)2^{m-j+1}) \frac{2^{-m-2+j}}{1-2^{-m-2+j}}$

mathe

最后的公式相对已经算很简单了。不过从这个公式我们还是不能得出P(m+2)在m趋向无穷时的行为。也许极限更本就不存在。