概率计算问题

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)$ $

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趋向无穷时的行为。也许极限更本就不存在。