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

mathe

http://zhidao.baidu.com/question/60176364.html 中有个问题:
抛硬币100次，出现10次以上连续正面的概率是多少？
我们将它推广一下,抛硬币n次,其中出现过t次连续正面的概率是多少?

已添加到A066178

mathe

shshsh的应该没有错，现在我来推导一下。
我们需要计算硬币抛n次过程中出现t次连续正面的概率。
我们对抛硬币过程中出现的状态进行分类：
其中$s_0$表示还没有出现t次连续正面的情况，而且当前最后一次硬币出现状态为反面或初试状态。
其中$s_1$表示还没有出现t次连续正面的情况，而且当前最后一次硬币出现状态为正面但是最后才连续1次正面
其中$s_2$表示还没有出现t次连续正面的情况，而且当前最后一次硬币出现状态为正面而且最后正好连续2次正面
...
其中$s_{t-1}$表示还没有出现t次连续正面的情况，而且当前最后一次硬币出现状态为正面而且最后正好连续t-1次正面
其中$s_t$表示已经出现t次连续正面的情况。
所以开始抛硬币之前处在状态$s_0$,然后抛硬币过程中，如果当前状态为$s_k$,其中k<t,那么抛一次硬币有$1/2$的概率
转移到$s_0$,还有$1/2$的概率转移到$s_{k+1}$;而如果当前状态为$s_t$,那么状态永远不会再改变。
所以我们可以得到状态转移矩阵M为
$[(1/2,1/2,1/2,...,1/2,0),(1/2,0,0,...,0,0),(0,1/2,0,...,0,0),(0,0,1/2,...,0,0),(...,...,...,...,...,...),(0,0,0,...,1/2,1)]$
其中我们知道对于初试状态，状态只可能为$s_0$,对应概率分布为$b=[(1),(0),(0),(...),(0),(0)]$
其中b是一个长度为t+1的列向量，b的第h个分量表示状态在$s_{h-1}$的概率
而经过k步以后，状态分布的概率变化为$M^k b$
而我们需要的值为经过n步以后到达状态$s_t$的概率，也就是$M^n b$最后一个分量，或者我们记
$u=(0,0,0,...,0,1)$
那么所求的结果就是$a_n = u M^n b$
为此我们可以先对矩阵M进行分析，由于矩阵2M更加简单，我们改为分析矩阵
$2M=[(1,1,1,...,1,0),(1,0,0,...,0,0),(0,1,0,...,0,0),(0,0,1,...,0,0),(...,...,...,...,...,...),(0,0,0,...,1,2)]$
而矩阵2M的特征多项式很简单，为
$g(x)=(2-x)(1+x+...+x^{t-1}-x^t)$
$={(x^{t+1}-2x^t+1)(2-x)}/{x-1}$
所以矩阵M的特征多项式为$f(x)=g(2x)$
所以我们知道如果计算结果为$a_n$,
我们知道数列一个特征根为1，而由于n趋向无穷时$a_n->1$，
可以假设$a_n=1+u_1 ({x_1}/2)^n+u_2 ({x_2}/2)^n+...+u_t ({x_t}/2)^n$
其中$x_1,x_2,...,x_t$时方程$x^{t+1}-2x^t+1$除去1以后的n个根
我们可以假设$b_n=2^n (1-a_n)$
那么我们可以知道${x^{t+1}-2x^t+1}/{x-1}$是数列$b_n$的特征多项式
也就是说，数列$b_n$满足递推式$b_{n+t+1}=2b_{n+t}-b_n$或者$b_{n+t}=b_{n+t-1}+b_{n+t-2}+...+b_n$,这个应该就是所谓的广义Fibonacci数列

mathe

也就是为了对于给定的t,如果我们要计算对应通项公式，可以通过解方程$x^{t+1}-2x^t+1=0$的所有解，然后就可以有通项公式了。
谁来数值计算一下$F_102^{(10)}$和$F_1002^{(10)}$?
其中$F_0^{(10)}=0,F_1^{(10)}=1,F_2^{(10)}=1,F_3^{(10)}=2,F_4^{(10)}=4,F_5^{(10)}=8,F_6^{(10)}=16,F_7^{(10)}=32,F_8^{(10)}=64,F_9^{(10)}=128,F_10^{(10)}=256,F_11^{(10)}=512,F_12^{(10)}=1023$
而$F_{n+11}^{(10)}=2F_{n+10}^{(10)}-F_n^{(10)}$
而抛100次，存在连续正面10次以上的概率为${F_102^{(10)}}/{2^100}$

mathe

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

至于那个分式 = 0.9558627713595783

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

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

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

而对于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

晕，突然发现这个问题中特征方程$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

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

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