数学研发论坛

标题: 抛硬币出现连续正面的概率 [打印本页]
作者: mathe    时间: 2008-7-18 16:12
标题: 抛硬币出现连续正面的概率
[jh]有趣且有难度的问题[/jh]http://zhidao.baidu.com/question/60176364.html 中有个问题:
抛硬币100次，出现10次以上连续正面的概率是多少？
我们将它推广一下,抛硬币n次,其中出现过t次连续正面的概率是多少?

已添加到A066178
作者: shshsh_0510    时间: 2008-7-18 16:52
是这个吗，但没有推导过程：

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___    时间: 2008-7-18 17:30
这个问题貌似可以这样，我们设M(x,y)为在长度为x的01序列中含有长度为y的1序列的总个数。可以看到如果能求M，问题就差不多了。M的样子如下：
(, 下载次数: 116)
我们可以看到，M的每一行（不为0的部分）满足：M(x)=2M(x-1)-M(x-3)+2^(x-3)。
作者: mathe    时间: 2008-7-18 18:10
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    时间: 2008-7-18 18:29
也就是为了对于给定的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}$
作者: 无心人    时间: 2008-7-18 19:17
$F_102^{(10)} = 1211700015849788251502892752696 $

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

至于那个分式 = 0.9558627713595783

所以投100次硬币出现连续10次以上的概率为1-0.9558627713595783=0.0441372286404217
作者: 无心人    时间: 2008-7-18 21:12


有米不用迭代的函数式语言？
算这种东西很费时间的
虽然比写个C程序要快，且无须调试
作者: mathe    时间: 2008-7-19 08:10
呵呵，计算受不了了？那么我们看看能否得到更好用的公式。
我们现在看看能否给出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    时间: 2008-7-19 08:19
其中$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    时间: 2008-7-19 08:33
而对于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$
110.50222005921650437539314900083299
211.0039472560945626042296717505261
322.0069092711912102894563100627129
444.0118490272698787619203081600742
588.0197609571323822998698197638132
61616.031651583188626895454838284701
73232.047570227910457178387829251568
86464.063690018678506437470207581223
9128128.06451002750246161567818042825
10256256.00334173386700758850659443979
11512511.75545016205159804636690872342
1210231023.0086802648866917173406684459
1320452045.0134132736788208304516651412
1440884088.0199172761664313714470202193
1581728172.0279855250629839809737322779
作者: 无心人    时间: 2008-7-19 14:45


倒不是受不了
是破编译器进行规约
会扯出一个很大的递归调用的
规约图，然后实际的计算可能还不
到规约花费时间的1%
作者: mathe    时间: 2008-7-19 17:45
晕，突然发现这个问题中特征方程$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    时间: 2008-7-19 19:26
上面的分析中关系弄错了。但是两者特征多项式一样是没有错误的，应该可以利用这个信息得到一些结论。
作者: 无心人    时间: 2008-7-19 20:58
呵呵
作者: vvipi    时间: 2008-7-19 21:25
非常感谢M版的热心！这个问题困扰我快一个月了，一直找不到答案。因为自己写的一篇小东西里面需要用到几个数据，一直计算不出来，经过搜索也没有找到满意的答案，所以在网络上提问求助。数学真的是一门很有趣的学科，能在秩序和逻辑上给人一种完美的感觉，不过对我这种绞尽脑汁想不出答案的人来说就比较痛苦了，呵呵。我数学基础比较差，先试试看能不能消化这个思路，如果消化不了，可能还要厚着脸皮请大家帮忙把50、200、400、800、5000和10000次的数据算一下了。
作者: 无心人    时间: 2008-7-19 22:10


倒
精确值还是免了
算10000的还不要一年阿
作者: mathe    时间: 2008-7-20 08:57
原帖由 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}$
(, 下载次数: 10)
如果仅仅需要近似值，那么很简单，使用上面的近似公式就可以了
结果转化为公式
$~=1-1.0039472560945626042296717505275*0.9995093163550505693317046195645^n$
有了这个公式，你可以计算更多项的结果。而上面公式误差保证小于$1/2^{n-1}$(但是由于上面数字本身精度的限制，精度又不会高于$31-lg(n)$)
nProb$~=$
500.020389972229054349368428467695516
2000.089918686340675823367849723639161
4000.17500845543038383957014507013382
8000.32206493470683517420512398683463
50000.913713391064835162429300274003
100000.99258389438655053993775098859373
200000.99994521761762287616869920111126
作者: 无心人    时间: 2008-7-20 09:16


你家也有linux么？
作者: mathe    时间: 2008-7-20 09:19
原帖由 无心人 于 2008-7-20 09:16 发表


你家也有linux么？

我干嘛用家里的？
作者: 无心人    时间: 2008-7-20 09:21
周末你不在家你跑研究所？
真是敬业阿
作者: vvipi    时间: 2008-7-20 09:58
多谢了！我只要4位左右的近似值就可以了。太感谢了，小激动，哈哈。
原帖由 mathe 于 2008-7-20 08:57 发表

不知道你要的是精确值还是近似值。
如果要精确值，那么还是使用递推数列计算$F_n^{(10)}$最方便，附件压缩包中fb10.txt给出了所有你需要的n对应的$F_{n+2}^{(10)}$的值，fb10.c给出计算它们的源代码（需要gmp库的 ...
作者: 无心人    时间: 2008-7-20 10:03
mathe:

55555555555
别克扣我鲜花阿
多不容易赚阿

那你的地址，用户名，密码给俺一份
限制权限的我也要，我自己的服务器
速度太低
作者: mathe    时间: 2008-7-20 14:59
呵呵，给你密码你也进不去。
作者: mathe    时间: 2008-7-20 15:07
10#中估计公式的误差发现有很漂亮的写法:
$1/{2pii}oint_{|z|=1}{(z-1)z^{n+t-2}}/{z^{t+1)-2z^t+1}dz$
而类似的，我们也可以有
$b(n)=1/{2pii}oint_{|z|=2}{(z-1)z^{n+t-2}}/{z^{t+1)-2z^t+1}dz$
作者: 无心人    时间: 2008-7-20 15:35
7
小气
俺不稀罕呢
作者: mathe    时间: 2008-7-21 09:39
原帖由 mathe 于 2008-7-20 15:07 发表
10#中估计公式的误差发现有很漂亮的写法:
$e(n)=1/{2pii}oint_{|z|=1}{(z-1)z^{n+t-2}}/{z^{t+1)-2z^t+1}dz$
而类似的，我们也可以有
$b(n)=1/{2pii}oint_{|z|=2}{(z-1)z^{n+t-2}}/{z^{t+1)-2z^t+1}dz$


上面这个积分式我们换一种形式就是函数
${z-1}/{z^{t+1}-2z^t+1}$分别在区域$1<|z|<2$和$|z|>2$中罗兰展开式中$1/{z^n}$的系数,也就是我们将这个问题转化回为特征函数问题
作者: mathe    时间: 2008-7-21 14:21
为了证明10#中公式
$b(n)=[{r^{-1}(r-1)}/{(t+1)r-2t}r^n]$,这里$[x]$代表最接近x的整数
我们先证明
${r^{-1}(r-1)}/{(t+1)r-2t}<1/2$
其中1<r<2而且$r^{t+1}-2r^t+1=0$ ,
首先我们容易得出$(t+1)r-2t>0$
这个是因为方程$h(x)=x^{t+1}-2x^t+1$中，显然$h({2t}/{t+1})<0,h(2)>0$,而且前面已经证明r是h(x)唯一一个绝对值大于1的解，所以${2t}/{t+1}<r<2$
所以我们需要证明$2(1-r^{-1})<(t+1)r-2t$也就是$(2-r)r<2/{t+1}$
由于我们知道$r^t(2-r)=1$,所以只要证明$r^{t-1}>{t+1}/2$也就是$r>root{t-1}{{t+1}/2}$（其中$t>=2$）
而其中右边容易得出在$t=2$时有最大值1.5,而$r>{2t}/{t+1}$,所以在t>=4时都已经有不等式成立。
而对于t=3时，我们知道$r_3=1.83...>1.5$,对于t=2,$r_2=1.618...>1.5$
所以我们证明了${r^{-1}(r-1)}/{(t+1)r-2t}<1/2$
而更加容易的，我们可以证明$(r-1)/{(t+1)r-2t}>1/2$ (这个等价于r<2),
而又有前面的不等式得到$(r-1)/{(t+1)r-2t}<r/2<1$
作者: mathe    时间: 2008-7-21 14:29
现在我们定义序列$e(n)=b(n)-{r^{-1}(1-r)}/{2t-(t+1)r}r^n$也就是这个误差，其中对于所有的$n>=-t+2$全部定义。
而其中$b(n)$在$n<=0$时定义为$b(-t+2)=b(-t+3)=...=b(0)=0$(这样所有这些项都可以用同一个递推公式推导了)
显然$e(n)$也满足递推公式$e(n+t)=e(n+t-1)+e(n+t-2)+...+e(n)$,这个递推式对于所有的$n>=-t+2$都成立。
而且我们知道$e(0)=b(0)-{r^{-1}(1-r)}/{2t-(t+1)r}=-{r^{-1}(1-r)}/{2t-(t+1)r}$,所以$-1/2<e(0)<0$
同样，我们知道$-1/2<e(-1)<0,-1/2<e(-2)<0,...,-1/2<e(-t+2)<0$
而$e(1)=1-{r-1}/{(t+1)r-2t}$,所以$0<e(1)<1/2$
作者: mathe    时间: 2008-7-21 14:36
我们现在定义一个模型，有一个人在实数轴的整点上行走（开始坐标大于1），他每次分别以均等的概率随机后退t格或前进1格，知道到达坐标位置$[-t+2,1]$之间停止；如果他最后停留在坐标x,那么我们说他最终的得分为$e(x)$,那么请问如果他的起始坐标为x,那么他最终得分的期望值是多少呢？(容易证明他最终会停止下来的概率为1)
非常有意思，对于任何一个位置n,他最终得分的期望值为$e(n)$,由于每个最终得分都在$-1/2$和$1/2$之间，我们可以知道所有的$e(n)$也必然只能在$-1/2$和$1/2$之间。也就是这种方法可以证明上面的猜想。

这个是因为假设开始在位置n的得分为$f(n)$,我们知道对于任意$n>=2$有$f(n)={f(n+1)+f(n-t)}/2$或者说$f(n+1)=2f(n)-f(n-t)$,而且对于$n<=1$有边界条件$f(n)=e(n)$
根据$f(n)$的递推公式我们知道它对应的特征方程为$x^{t+1}-2x^t+1$,这个方程有一个根的绝对值大于1，还有一个根为1，其余t-1个根绝对值小于1，根据
http://bbs.emath.ac.cn/thread-354-1-1.html 中的结论，由于数列$f(n)$有界，那么绝对值大于1的根所对应的项的系数必然为0。也就是$f(n)$的通项公式可以由其余t个特征根决定，也就是前t项已经唯一决定了数列$f(n)$,而由于$e(n)$也满足同样递推式，必然得出$f(n)=e(n)$
作者: mathe    时间: 2008-7-21 14:48
由此我们可以得到
$b(n)="round"({r^{-1}(r-1)}/{(t+1)r-2t}r^n)$
而抛硬币n次出现连续t次正面的概率为
$p(n)=1-{"round"({r-1}/{(t+1)r-2t}r^{n+1})}/{2^n}; r>1&&r^{t+1}-2r^t+1=0$
作者: mathe    时间: 2008-8-25 09:44
Now we could summarize how the formula of t-step Fibonacci sequence is got.
In 9#, we got the characteristic polynomial of
the Linear recurrence equation of the t-step Fibonacci sequence: ${x^{t+1}-2x^t+1}/{x-1}$.
According to link solutions of equation $x^m=2-x^{-n}$, we could use Rouché's Theorem to prove that there's
only one root of polynomial $x^{t+1}-2x^t+1$ whose norm is greater than 1 and t-1 roots whose norms are less than 1. And obviously, the root with greatest norm is a real root greater than 1.
Let's assuming that the real root greater than 1 is r, and besides from $1/{z_0}=1$ and $1/{z_1}=r$, there're another t-1 roots of polynomial $x^{t+1}-2x^t+1$. Let's assuming they're $1/{z_2},1/{z_3},...,1/{z_t}$. And it is obvious there're no multiple roots.
So that we could write the n'th item of the t-step Fibonacii sequence in the form: $u_1z_1^{-n}+u_2z_2^{-n}+...+u_{t}z_t^{-n}$, and we got that $u_s={z_s-1}/{2t-(t+1)z_s^{-1}}$
Now let's assuming $e_n = F_n^{(t)} - u_1 z_1^{-n} = u_2z_2^{-n}+...+u_{t}z_t^{-n}$, so we know that the characteristic polynomial of $e(n)$ is ${x^{t+1}-2x^t+1}/{(x-1)(x-r)}$.
In 30#, a probability modeling is used to prove that $|e(n)|<1/2$.
Let's assuming a man is randomly walking in an axis. He starts from a positive integer location in the axis and each time he random walks towards the positive direction by 1 or towards the negative direction by t with equivalent probability.
And he will stop when he reached a point whose coordinate is no more than 1. We will give a score $e(x)$ to him when he finally stops at coordinate x.
We know the probablity that he will finally stop is 1 when t is no less than 1. It is interesting that we could find that the expected score is $e_n$ when he starts from point whose coordinate is n.
In 29# it is proved that the absolute values of all those final scores ($e(-t+2)$ to $e(1)$) are less than $1/2$, so we proved that $|e_n|<1/2$ for all $n>=-t+2$
So we know now that $F_n^{(t)}$ could be represented by $"round"(u_1 z_1^{-n})$, or $F_n^{(t)}="round"({r-1}/{(t+1)r-2t}r^{n-1})$ for any $n>=-t+2$, where r is t-bonacci constant.
作者: zhangjianquan    时间: 2009-2-11 12:37
高手,我想问一个问题,如果此个题100次趋于无穷大,请求出多大次数的连续正面的概率为最大?
作者: mathe    时间: 2009-2-13 08:21
你这个是个不同的问题,很简单.连续出现t次正面的概率为$1/{2^t}$,所以出现一次的概率最大,为1/2
作者: shangwen_ren    时间: 2009-3-9 17:14

whoops... i just did something silly... fortunately the posted comment can be edited...
作者: AAAAA    时间: 2012-2-11 13:43
其中$z_1^{-1}$我们可以通过取初试值为$1/2$然后用牛顿迭代法得到
记$r=z_1^{-1}$
而递推式中其他各式绝对值都远远小于，所以我们得到，对于n充分大
$b(n)="round"({r^{-1}(1-r)}/{2t-(t+1)r} r^{n})$
mathe 发表于 2008-7-19 08:19

此公式非常漂亮。
请教mathe：此公式是只有正反两种情况下的计算方法，是否能推广为m种情况的计算公式？
即：n　个　大　小　相　同　的　小　球　排　成　一　排，给　每　个　球　涂　上　m　种　颜　色　的　一　种，要　求　相　邻　颜　色　相　同　小　球　个　数　小　于　t　个，问　有　几　种　不　同　涂　法？
作者: AAAAA    时间: 2012-2-12 11:32
上面叙述有点问题，其中相邻颜色是指定的一种颜色（m种颜色中一种）。
作者: AAAAA    时间: 2012-2-14 21:55
请教mathe：是否能推广为m种情况的计算公式？
即：n　个　大　小　相　同　的　小　球　排　成　一　排，每　个　球　的　颜　色　为　m　种　颜　色　的　一　种，如　果　相　邻　小　球　颜　色　为　指　定　的　一　种　颜　色（m种颜色中一种）时，这　些　相　邻　小　球　个　数　小　于　t　个，问　有　几　种　不　同　排　列　方　法？
作者: 沉默的见证    时间: 2012-2-15 12:42
我自己演算的16次抛硬币里面，无法出现连续2次正面的几率：
0.0049591064453125

请老大用公式演算一下
作者: AAAAA    时间: 2012-2-17 09:15
我自己演算的16次抛硬币里面，无法出现连续2次正面的几率：
0.0049591064453125

请老大用公式演算一下
沉默的见证 发表于 2012-2-15 12:42

按老大计算公式，无法出现连续2次正面的几率=0.039428711
你的计算有问题
作者: liuxiaof    时间: 2012-9-2 08:25
问一下，有一人，抛硬币直到出现连续7个正面为止，问他抛了n>=7次出现以上情况的概率
作者: zsm325800    时间: 2012-9-23 10:39
好几年前就关注这个问题，根据楼主推导，用matlab编出来了，谢谢楼主
作者: zsm325800    时间: 2012-9-23 10:40
问题可做进一步推广，比如单次正面概率p不等于0.5的情况又如何？
作者: zsm325800    时间: 2012-9-24 13:14
楼主在第4楼的发言提供了很好的基本思路！
推广：
以p代替概率1/2，
直接编程运算Plianxu(n,t,p),概率转移矩阵M可以稍微改动，
1<=j<=t,     M(1,j)=1-p;
t+1<=j<=n+1,    M(1,j)=0;
2<=i<=t,    M(i,i-1)=p;
t+1<=i<=n+1,    M(i,i)=1;   运用MTALAB运算，可以比较容易得出n<=1000下的概率
作者: 杨圆圆    时间: 2012-10-26 10:56
楼主求的是至少5次连续出现正面，如果要求连续5次正面，应该是p（至少5次）-p（至少6次），这样减出的结果有可能分别求出连续2、3次的概率，有可能p（2）<p（3），谁能解释下原因
作者: lianghr    时间: 2013-1-20 15:17
问一下，m次实验中连续出现n次正面的概率。有公式吗
作者: AAAAA    时间: 2013-1-21 09:37
问一下，m次实验中连续出现n次正面的概率。有公式吗
lianghr 发表于 2013-1-20 15:17


不知你要的是怎样的公式？
简单公式肯定是没有的，现在世上最好的公式是楼主在31#楼给出的公式。其中，n对应你的m；t对应你的n。如果m和n都不大，求解高次方程解有难处，也可按楼主在4#楼给出的矩阵公式计算：
p(m,n)=uM^mb
作者: kastin    时间: 2013-12-12 20:36
一般情况的公式Run
只不过上面给出的是生成函数的方法。我有一种思路大家看看：
问题  试验中事件A发生的概率设为p, 那么n次独立重复试验中，至少连续发生r次的概率P(r,n)为多少？
由于至少连续发生r次，也就是说，至少存在一个不少于r次的连续事件发生，且剩余中可以存在一系列分隔开的连续发生事件(次数可以小于r，也可以大于或等于r)。因此，原始问题就相当于至多连续发生r次，r+1次，r+2次，...，n次的概率之和。
作者: dasaint    时间: 2015-8-7 16:42
这个r应该怎么算呢？
作者: wayne    时间: 2018-12-20 17:45
好老的帖子。发生在我进入论坛之前,盘古开天地的时候。
这个完全是被sheng_jianguo在帖子 https://bbs.emath.ac.cn/thread-15625-1-1.html 带逛过来的，

我来计算一下，答案是精确值 $6993823047305143749226306585/158456325028528675187087900672 = 0.0441372286404216877406785935788813088029671991207867937263842...$，与6#，7#的计算完全吻合。
附注Mathematica代码：
  1. t=10;m=DiagonalMatrix[ConstantArray[1/2,t],-1,t+1];
  2. m[[1]]=ConstantArray[1/2,t+1];m[[1]][[t+1]]=0;m[[t+1]][[t+1]]=1;
  3. MatrixPower[m,100][[-1,1]]
复制代码


作者: Zereke    时间: 2019-3-18 13:42
博主你好，如果硬币正面概率为p，按照4楼方法求解，这个问题的解是否有通式？
作者: sheng_jianguo    时间: 2019-3-18 14:58
Zereke 发表于 2019-3-18 13:42
博主你好，如果硬币正面概率为p，按照4楼方法求解，这个问题的解是否有通式？

你的问题本论坛好像讨论过，参见：请教大家一个复杂概率问题
作者: Zereke    时间: 2019-3-18 15:16
sheng_jianguo 发表于 2019-3-18 14:58
你的问题本论坛好像讨论过，参见：请教大家一个复杂概率问题

我知道用软件可以实现，但是我想问有没有解析解？类似于F(k)N+2/2^N这种解的？

补充内容 (2019-3-19 10:50):
明白了，多谢@mathe
作者: 人教版高中    时间: 2020-3-8 09:05
楼主你好，最近刚好研究到这个抛硬币的问题。请问下面这个题：在连续出现t次反面前出现m次正面的概率怎么求呢？感觉就相当于两个子问题拼接起来。



欢迎光临 数学研发论坛 (https://bbs.emath.ac.cn/) Powered by Discuz! X3.5