概率计算问题

mathe

在百度贴巴看到一道题目:http://tieba.baidu.com/f?kz=271888843 给定n枚理想硬币（投出后落下出现正面和反面的概率都是1/2,而且多次投币相互独立）， 将它们投出落下后，如果最多只有一枚硬币是正面的，那么终止投币过程； 不然将所有正面的硬币重新拿起投币，直到最后最多只有一枚硬币是正面然后终止投币过程。 请问，终止投币过程后所有硬币都是反面的概率是多少。 关于这个问题，如果我们记这个概率为$P(n)$,那么对于$n>=2$显然可以有递推公式 $P(n)={C_n^n P(n)+C_n^{n-1}P(n-1)+...C_n^2P(2)+1}/{2^n}$ 或者可以改写成 $P(n)={C_n^{n-1}P(n-1)+...C_n^2P(2)+1}/{2^n -1}$ 其中 $C_n^k={n!}/{k!(n-k)!}$是组合数 请问 i)是否可以给出P(n)的通项公式 ii)如果i)做不到，那么能否证明P(n)极限存在，并且计算出极限（精度越高越好，最好同时给出上界和下界） iii)对于给定n,高精度计算P(n),最好用分式形式表示（然后同时高精度计算出P(n)小数部分前若干位，可以让我们容易看出极限大概是多少）

mathe

如 $P(100)=24212446619604703964441826177335297220274449489972076243282466806885467009002302420772364878794120366192101713664920601387969963974432880752998958353280020778633678106902984948507810902801577855066119015595224092318438287724123872148137230732786372775030725692126513307366889445305466891974034279027936108023620704479223060977983696005277691754366902188718670923141205947251146774230993466200627725413565384290126483924592106503485767902358528816684898374018631553846405773953203872157306130829877446029667339031807903680203964816831272115211405170815623120980810753564575523248317976948241565870782213224286486001874113008768019206206737785663949077800601918364647637904364739392820836200460951752732369196484427327718994277392645539780749079004073711135393000406392514321615544766925388881666320089145516647845335495489778932008644286652534353914320833464709590252568525424299011104837527/86892064279492453953188039648187133334016414403874605165793915801213956772656166517539872814657519043503730828124464647673414852936009548075772881250175976560263407433825694658916832128958154801811841312392669310267956415090926520793270433785315356585513778150072989636862246760300455530349881323266836600414981325512923835697446109043370344650170033834847719739217764180203723309543189563413799270524852652673694333430784981501004469385298881607442883928128633834952061989755616387861671386393210001155450626048953943271575507984786499318923920444756186659511566552332139050931523720014886264749259665189174978677777661807919432101541602177880774148088728531361612430544375585266902505009650854008931537438449984971759466224084364168665063565901302922285567268108340098687899223563586659152304055907858269892070717015278007341200438037828696715806927256523797229075194867698563806844410715$ 分子分母都已经很大了，再计算下去速度就很慢了。 而用浮点形式，计算可得P[1000]=0.278647 所以我们知道如果2中极限不是0，应该小于0.278647 (看上去P(n)应该单调减，能否证明呢?)

mathe

上面结论错了，从前1000个计算结果来看，计算结果并不单调（如果认为计算累计误差没有影响到计算结果的话）

无心人

这么大么？

mathe

是的，所以看来通过使用有理数计算不是一个好办法。我使用gmp的话，计算到将近第300项就动不了了（越来越慢）

无心人

精度太高闹的 应该是100位浮点足够了

mathe

不过浮点计算速度太慢，比如用double类型数据，算到1000项看上去也就精确到6位有效数字（而且不知道是否是极限），而我试着计算10000项，发现要很长时间。所以如何提高计算速度也是问题。

无心人

应该没极限 如果有就恐怖了

mathe

极限是否存在不知道。 我得出一个比较有意思的计算方法，这个方法用于实际计算应该还行。 记 $F(x)=x^2/2(1/{2-x} + \sum_{n=1}^{+infty} 2^n/{(2^{n}(1-x)+x)^2(2^(n+1)(1-x)+x)})$ 那么如果将F(x)在x=0展开成泰勒级数，其第K项系数就是P(K)

无心人

展开后复杂么