抛硬币出现连续正面的概率

无心人

呵呵

mathe

上面的分析中关系弄错了。但是两者特征多项式一样是没有错误的，应该可以利用这个信息得到一些结论。

mathe

晕，突然发现这个问题中特征方程$x^{t+1}-2x^t+1$是随机游走中的概率问题中进t退1的特殊情情况,最后可以得出我们使用上面的近似公式那么b(n)的误差为$q(n)-q(n+1)$,其中q(n)是那个问题中5#中定义的当A在B后面n步时能够返回原点的概率.所以我们只要能够证明$0<q(n)<1/2$那么就证明了只使用一项然后四舍五入的方法是正确的。而且也可以解释上面例子中除了第一项以外，后面所有项的误差都是正的情况（因为q(n)应该是单调的）而且显然对于固定的n,q(n)关于t是递减的，所以如果我们能够对于t=2的情况计算出$q(1)<=1/2$,那么对于所有这一类题目，都能够直接使用那个近似计算方法，然后四舍五入，而结果就会是精确的.

无心人

倒不是受不了
是破编译器进行规约
会扯出一个很大的递归调用的
规约图，然后实际的计算可能还不
到规约花费时间的1%

mathe

而对于t=10,使用计算器就可以算出r=1.9990186327101011386634092391292
所以$b(102)~=1211700015849788251502892752685.8,b(1002)~=6.5849587983847754109895686668823e+300$
而投100次不出现连续10个正面的概率为${b(102)}/{2^100}=0.95586277135957831225932140641244$,
而投1000次不出现连续10个正面的概率为${b(1002)}/{2^1000}=0.61455024758751836408966755676318$,

而对于公式$b(n)="round"(u_1 r^n)$,计算前面若干项我们可以发现猜想均成立:

n	b(n)	$u_1r^n$
1	1	0.50222005921650437539314900083299
2	1	1.0039472560945626042296717505261
3	2	2.0069092711912102894563100627129
4	4	4.0118490272698787619203081600742
5	8	8.0197609571323822998698197638132
6	16	16.031651583188626895454838284701
7	32	32.047570227910457178387829251568
8	64	64.063690018678506437470207581223
9	128	128.06451002750246161567818042825
10	256	256.00334173386700758850659443979
11	512	511.75545016205159804636690872342
12	1023	1023.0086802648866917173406684459
13	2045	2045.0134132736788208304516651412
14	4088	4088.0199172761664313714470202193
15	8172	8172.0279855250629839809737322779

mathe

其中$z_1^{-1}$我们可以通过取初试值为$1/2$然后用牛顿迭代法得到
记$r=z_1^{-1}$
而递推式中其他各式绝对值都远远小于，所以我们得到，对于n充分大
$b(n)="round"({r^{-1}(1-r)}/{2t-(t+1)r} r^{n})$
而我怀疑这个表达式对所有的n都成立，不过还没有验证，但是如果仅仅数值计算，不需要精确值，由于|r|接近2，而其他项都递减，所以用上面公式精度已经非常高了。

然后我们在对仅仅使用$b(n)~={r^{-1}(1-r)}/{2t-(t+1)r} r^{n}$做一下误差分析。
我们知道除了上面一项以外，实际上还有t-1项$u_s z_s^{-n}, s=2,3,...,t$.
其中对于$n>=1$,有$|u_s z_s^{-n}|<=|u_s*z_s|<={1+|z_s^{-1}|}/{|2t-(t+1)|}<2/{t-1}$
所以t-1项之和的绝对值小于$(t-1)*2/{t-1}=2$
也就是说使用这个公式$b(n)$的误差小于2. 而则换成计算概率，第n项的计算误差小于$1/{2^{n-1}}$，对于比较大的n仅使用第一项计算精度非常高，实际计算过程中可能r采用的精度都没有这么高。

mathe

呵呵，计算受不了了？那么我们看看能否得到更好用的公式。
我们现在看看能否给出k阶Fibonacci数列$b(n)=F_n^{(t)}$的通项公式
我们采用初试值$b(-t+2)=b(-t+3)=...=b(0)=0,b(1)=1,b(2)=1$
为了方便起见，我们可以定义$b(-t+1)=1$,在这样定义以后b(1)的值也可以通过递推公式来递推得到了。
我们定义$h(y)=y^{t+1}-2y+1=k(y)(y-1)$,那么我们知道${h(1/y)y^{t+1}}/{y-1}$是数列的特征方程，所以$h(y)$的所有根是数列特征值的倒数。
对于复平面上的圆$|z|=d$其中$sqrt(2/3)<=d<1$,我们有
$|z^{t+1}|=d^{t+1}<=2d-1<=|2z-1|$
所以根据儒勒定理，我们知道$h(y)$在圆$|z|<=d$内部解的数目同方程$-2z+1=0$的数目相同。也就是在$|z|<1$内方程$h(z)=0$只有一个解。而如果|z|=1满足h(z)=0,那么容易得到z=1,而且根的重数为1。
由此我们得到h(z)有一个根在单位圆内部，t-1个根在单位圆外部，还有个根1。
假设单位圆内部根为$z_1$,单位圆外部的根为$z_2,z_3,...,z_t$,于是我们可以假设数列$b(n)$的通项公式为
$u_1z_1^{-n}+u_2z_2^{-n}+...+u_{t}z_t^{-n}$
其中$u_1,u_2,...,u_t$为待定系数。
采用类似 随机游走中的概率问题可以得到其中
$u_s=1/{k'(z_s)}$
而我们知道
$k(z)=(z-z_1)(z-z_2)(z-z_3)...(z-z_t)$
$k'(z_s)=\prod_{h!=s} (z_s-z_h)$
$h'(z_s)=(z-1)\prod_{h!=s} (z_s-z_h)$
所以$k'(z-s)={h'(z_s)}/{z_s-1}$
$u_s={z_s-1}/{h'(z_s)}$
而$h'(z_s)=(t+1)z_s^t-2=(t+1)(2-z_s^{-1})-2=2t-(t+1)z_s^{-1}$
所以
$u_s={z_s-1}/{2t-(t+1)z_s^{-1}}$

无心人

有米不用迭代的函数式语言？
算这种东西很费时间的
虽然比写个C程序要快，且无须调试

mathe

原帖由 无心人 于 2008-7-18 19:17 发表
$F_102^{(10)} = 1211700015849788251502892752696 $

至于那个分式 = 0.9558627713595783

所以投100次硬币出现连续10次以上的概率为1-0.9558627713595783=0.0441372286404217

无心人

$F_102^{(10)} = 1211700015849788251502892752696 $

至于那个分式 = 0.9558627713595783