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

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

无心人

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

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$,那么对于所有这一类题目，都能够直接使用那个近似计算方法，然后四舍五入，而结果就会是精确的.

mathe

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

无心人

呵呵

vvipi

非常感谢M版的热心！这个问题困扰我快一个月了，一直找不到答案。因为自己写的一篇小东西里面需要用到几个数据，一直计算不出来，经过搜索也没有找到满意的答案，所以在网络上提问求助。数学真的是一门很有趣的学科，能在秩序和逻辑上给人一种完美的感觉，不过对我这种绞尽脑汁想不出答案的人来说就比较痛苦了，呵呵。我数学基础比较差，先试试看能不能消化这个思路，如果消化不了，可能还要厚着脸皮请大家帮忙把50、200、400、800、5000和10000次的数据算一下了。

无心人

倒
精确值还是免了
算10000的还不要一年阿

mathe

原帖由 vvipi 于 2008-7-19 21:25 发表
非常感谢M版的热心！这个问题困扰我快一个月了，一直找不到答案。因为自己写的一篇小东西里面需要用到几个数据，一直计算不出来，经过搜索也没有找到满意的答案，所以在网络上提问求助。数学真的是一门很有趣的学科， ...

不知道你要的是精确值还是近似值。
如果要精确值，那么还是使用递推数列计算$F_n^{(10)}$最方便，附件压缩包中fb10.txt给出了所有你需要的n对应的$F_{n+2}^{(10)}$的值，fb10.c给出计算它们的源代码（需要gmp库的支持），而需要的概率就是
$1-{F_{n+2}^{(10)}}/{2^n}$
fb10.tar.gz (6.22 KB, 下载次数: 10)

2008-7-20 08:57 上传

点击文件名下载附件

如果仅仅需要近似值，那么很简单，使用上面的近似公式就可以了
结果转化为公式
$~=1-1.0039472560945626042296717505275*0.9995093163550505693317046195645^n$
有了这个公式，你可以计算更多项的结果。而上面公式误差保证小于$1/2^{n-1}$(但是由于上面数字本身精度的限制，精度又不会高于$31-lg(n)$)

n	Prob$~=$
50	0.020389972229054349368428467695516
200	0.089918686340675823367849723639161
400	0.17500845543038383957014507013382
800	0.32206493470683517420512398683463
5000	0.913713391064835162429300274003
10000	0.99258389438655053993775098859373
20000	0.99994521761762287616869920111126

无心人

你家也有linux么？

mathe

原帖由 无心人 于 2008-7-20 09:16 发表


你家也有linux么？

我干嘛用家里的？