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

mathe

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

shshsh_0510

是这个吗，但没有推导过程： http://mathworld.wolfram.com/CoinTossing.html "Similarly, the probability that no k consecutive tails will occur in n tosses is given by $F_(n+2)^((k))/2^n$, where $F_l^((k))$ is a Fibonacci k-step number." [ 本帖最后由 无心人 于 2008-7-18 17:07 编辑 ]

zgg___

这个问题貌似可以这样，我们设M(x,y)为在长度为x的01序列中含有长度为y的1序列的总个数。可以看到如果能求M，问题就差不多了。M的样子如下： 我们可以看到，M的每一行（不为0的部分）满足：M(x)=2M(x-1)-M(x-3)+2^(x-3)。

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$,其中k1$， 可以假设$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}$

无心人

$F_102^{(10)} = 1211700015849788251502892752696 $ 至于那个分式 = 0.9558627713595783

mathe

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

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

无心人

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

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采用的精度都没有这么高。