智游城

标题: 一道纯概率题 [打印本页]

作者: 伟大的墙 时间: 2010-11-30 01:53
标题: 一道纯概率题
巴萨和皇马德比238场，没有任何一个队连输5场过
我们假设两队势均力敌，每次交锋都各50的概率赢
那么238场比赛不出现5连输或更多连输的概率有多大

我感觉应该挺小的

作者: pokerbean 时间: 2010-11-30 03:54
本帖最后由 pokerbean 于 2010-11-30 04:33 编辑

应该是很小吧，

....

好象不太对

作者: Howard 时间: 2010-11-30 04:57
即使不考虑平局，只有胜负，这道题也比初看起来要复杂得多。

我的直觉是，这应该是个0.01%-1%之间的数。具体计算太复杂，我还没有理清头绪。谁能给出公式？

作者: 伟大的墙 时间: 2010-11-30 05:28
回复 3# Howard

话音未落
4；0

作者: 沙天马士 时间: 2010-11-30 05:37
一个硬币连抛238次，连续大于5次正面（反面）的可能性是多少，在用1减去这个数
连续大于5次正面（6次7次。。。）的可能性应该也就是连续5次正面可能性的零头儿可以忽略了，要不然得积分，所以就按连续5次正面算就差不多了，设这个可能性为X，墙这个题的答案就是（1-X），这个X算起来有点恐怖，留给楼下的朋友算吧

作者: 伟大的墙 时间: 2010-11-30 05:52
回复 5# 沙天马士

这个题要较真更复杂
除了平局因素外
每个队主场客场的胜率差出很多
再考虑这因素更复杂

作者: windstormm 时间: 2010-11-30 06:41
本帖最后由 windstormm 于 2010-11-30 06:47 编辑

这个算起来不容易，但可以用以下公式算(我和一同事讨论了半天得出的)。

p=1-(2^n-SUM^n_(i=k) [2^(n-i+1)])/2^n.
n is the total event number. K is the number of continuous event does not happen.
so for qiang's example. n=238. k=5.

其实最容易是做个simulation...

作者: 沙天马士 时间: 2010-11-30 07:20

这个算起来不容易，但可以用以下公式算(我和一同事讨论了半天得出的)。

p=1-(2^n-SUM^n_(i=k) [2^(n-i+1) ...
windstormm 发表于 2010-11-30 06:41

你哪找的公式，看起来挺像，想半天没做出来，我觉得需要有递归求和的过程，还需要2的次方运算，就是没理清
最简单的sample就是抛3次硬币，不会出现连续2次正面（反面）的概率，当然就是“正反正”“反正反”就是1/2^2, 25%的概率

作者: 沙天马士 时间: 2010-11-30 07:26
代进去有点问题 n=3,k=2 , i=1,2

作者: windstormm 时间: 2010-11-30 07:49
本帖最后由 windstormm 于 2010-11-30 07:54 编辑

自己推的...n=3 k=2, i =2,3 i goes from k to n

从前5个算起.. 一个一个往后移..

((2^5-2)*2-2)*2-2....
然后简化,延伸一下

作者: 沙天马士 时间: 2010-11-30 08:13
回复 10# windstormm

哦，没看清公式，这样算，p=1，实际应该0.25吧？还有个sample，3次coinflip，不会连续3次出现正面（反面）的概率应该是0.75，这个公式得1/3

作者: windstormm 时间: 2010-11-30 09:01
本帖最后由 windstormm 于 2010-11-30 09:03 编辑

(2^3-2^(3-3+1))/2^3=0.75.

sum i=k=3 到n=3, 只有一项..没看见错..

作者: 沙天马士 时间: 2010-11-30 09:10

(2^3-2^(3-3+1))/2^3=0.75.

sum i=k=3 到n=3, 只有一项..没看见错..
windstormm 发表于 2010-11-30 09:01

我傻了，我傻了，2的3次方我一直当6算

作者: lisa 时间: 2010-11-30 10:37
0.5的5次方，3%左右。

作者: fhtxn 时间: 2010-11-30 10:51
有意思的问题。

作者: xiaodd 时间: 2010-11-30 11:16
没见过赌场连开10把大？

作者: a1143144 时间: 2010-11-30 12:01
微积分40分，线性代数7分，概率56分的飘过。。。。

作者: quily 时间: 2010-11-30 16:00
真是好问题。

作者: Howard 时间: 2010-12-1 02:04
本帖最后由 Howard 于 2010-12-1 04:10 编辑

这个算起来不容易，但可以用以下公式算(我和一同事讨论了半天得出的)。

p=1-(2^n-SUM^n_(i=k) [2^(n-i+1) ...
windstormm 发表于 2010-11-30 06:41

你使用的这个SUM符号我不太理解，换成西格玛后是不是这样：
[attach]890[/attach]

如果是的话，化简后其实也就是
[attach]891[/attach]

分子也就是2^(1)到2^(n-k+1)的求和，也就是2^(n-k+2) -2

所以整个式子其实就是2^（2-k） - 2^(1-n)

我觉得应该没这么简单。回头再写。

-----------------回来了，继续-----------------------

还是没有太大的头绪，看楼下bean的吧先。

作者: pokerbean 时间: 2010-12-1 03:35
本帖最后由 pokerbean 于 2010-12-1 03:37 编辑

你哪找的公式，看起来挺像，想半天没做出来，我觉得需要有递归求和的过程，还需要2的次方运算，就是没理清 ...
沙天马士发表于 2010-11-30 07:20

我只能写出个递归的公式：

对特定一个队而言，连比n场至少有一个m连输的概率可以表示为一个分数，其分母为2^n；分子表示为
F(n,m)

F(n,m)=0 when n<m;
F(n,m)=1 when n=m;
F(n,m)=2*F(n-1,m)+2^(n-1-m)-F(n-1-m,m) when n>m

验算一下：
F(3,2)=3; 也就是说概率是3/8，注意这是对特定一个队输而言，如果不在乎输/赢的对称情况，最后结果要乘2，就是3/4，不出现的概率是1/4，跟你说的一样。

剩下的我就不管了，墙自己去算F(238,5)吧。

作者: 沙天马士 时间: 2010-12-1 04:04
回复 20# pokerbean

这式子看着靠谱

作者: Howard 时间: 2010-12-1 04:19

我只能写出个递归的公式：

对特定一个队而言，连比n场至少有一个m连输的概率可以表示为一个分数，其 ...
pokerbean 发表于 2010-12-1 03:35

赞F(n,m)=0 when n<m; 只有程序员才会写上这句话，让我想起一个程序员的笑话。

老婆问为什么晚上睡觉前要放杯水在床头，程序员老公说我半夜醒来口渴了喝，老婆又问，那为什么还要再放一个空杯子呢？
老公答：万一醒来不渴呢？

我也曾经是（不太成功的）程序员，这个笑话我第一次看的时候感同身受啊！

作者: 沙天马士 时间: 2010-12-1 04:20
回复 19# Howard

恩，风暴这个式子是会出现的概率，化简也没啥问题，2^（2-k） - 2^(1-n)
把墙的k=5，n=238套进去，得出1/8,感觉出问题了，n值很大的时候会出现的概率应该接近100%了

作者: 沙天马士 时间: 2010-12-1 04:21
恩，一看就是搞IT的

作者: Howard 时间: 2010-12-1 04:32

我只能写出个递归的公式：

对特定一个队而言，连比n场至少有一个m连输的概率可以表示为一个分数，其 ...
pokerbean 发表于 2010-12-1 03:35

思路挺不错的，但逻辑上感觉这个还是有问题。第二个和第三个公式等于说n跟m的差固定的时候，F(n,m)也是固定的。

但是显然F(3,2) 跟F（101，100）是不同的。F（3，2）是3/4，（只考虑两连输，不考虑谁输）而F（101，100）是非常非常接近0的，因为几乎不可能出现100连输。

作者: pokerbean 时间: 2010-12-1 04:52
老兄，你忘了分母是不同的。F(n,m)只代表分子

作者: windstormm 时间: 2010-12-1 05:13
简化得不错。是假设只有赢或输，没有平局。。

作者: windstormm 时间: 2010-12-1 05:52

恩，风暴这个式子是会出现的概率，化简也没啥问题，2^（2-k） - 2^(1-n)
把墙的k=5，n=238 ...
沙天马士发表于 2010-12-1 04:20

你肯定这次你算对了？

作者: Howard 时间: 2010-12-1 06:02
本帖最后由 Howard 于 2010-12-1 06:05 编辑

老兄，你忘了分母是不同的。F(n,m)只代表分子
pokerbean 发表于 2010-12-1 04:52

我前贴的确忘了分母。但F(n,m)代表分子的话，它应该是所有的（n场中至少出现连输m场的）组合数。我觉得这也不太对。根据你的公式2和3，能得出，F（m1+c，m1）=F（m2+c，m2），其中c为常数。

但F（4，2）<> F（5，3）。下面以不论输赢举例

F(4,2) 4场中至少出现连输2场：应该是14次，所有2^4=16种组合中只有 ABAB 和 BABA 不满足。

F(5,3) 5场中至少出现连输3场：应该是16次

AAA开头4种：
AAA AA
AAA AB
AAA BA
AAA BB

BBB开头4种：
BBB AA
BBB AB
BBB BA
BBB BB

AAA在中间4种，其中两种已经统计过，故有效2种：
A AAA A （无效）
A AAA B （无效）
B AAA A
B AAA B

BBB在中间4种，其中两种已经统计过，故有效2种：
A BBB A
A BBB B
B BBB A （无效）
B BBB B （无效）

AAA在结尾4种，，其中两种已经统计过，故有效2种：
AA AAA （无效）
AB AAA
BB AAA
BA AAA （无效）

BBB在结尾4种，，其中两种已经统计过，故有效2种：
AA BBB
AB BBB （无效）
BA BBB
BB BBB （无效）

故此共计有4+4+2+2+2+2 = 16种 “至少有三场连续”的组合。

作者: 沙天马士 时间: 2010-12-1 06:06
回复 28# windstormm

没错吧，n趋于无穷，这个式子是1/8,实际情况,n趋于无穷时应该是100%

作者: windstormm 时间: 2010-12-1 06:27
本帖最后由 windstormm 于 2010-12-1 06:36 编辑

思路是这样。。大家拍砖吧。

assume 10 coin flip.  我们不能有3 个以上连续。。分母是2^10 , 我们要算去掉3 个以上连续的。。
1 2 3                2^3-2
2 3 4             加一个4号位 *2.. 所以 (2^3-2)*2-2 减去2是正负和前面一样的。。
   3 4 5          同理  加一个5号位  所以 (（2^3-2)*2-2)*2-2
以此类推。。再简化一下，就得出了那个结果。。。。

EDIT.. 又想了想，好像那个-2 不对。。

EDIT2.. 恩。。好像没错。。每次减后有被2X

作者: Howard 时间: 2010-12-1 06:42
bean还有一句话我仔细琢磨也觉得有点问题

“注意这是对特定一个队输而言，如果不在乎输/赢的对称情况，最后结果要乘2” 这对于F（3，2），F（9，6）等等m大于n的一半时是成立的。

但如果m远小于n，则不成立。因为巴萨连输5场+和皇马连输5场+不是互斥事件。也就是说，一个238场比赛的实验中可能同时存在巴萨输8场，皇马输9场。

如果不在乎输赢对称，应该是乘以比2小，比1大的一个数，但是具体是多少我也说不清。

豆豆表生气，你还会用递归，我自己是一点思路也没有，只能是别人提出来以后挑毛病。

作者: 沙天马士 时间: 2010-12-1 08:10

思路是这样。。大家拍砖吧。

assume 10 coin flip. 我们不能有3 个以上连续。。分母是2^10 , 我们要算 ...
windstormm 发表于 2010-12-1 06:27

你的思路没发现有什么问题，然后按你这套思路我推了一遍，推出的就是霍华德简化后那个式子，不过我前面举了个反例，式子不成立，我就想，思路上会不会有leak？

作者: pokerbean 时间: 2010-12-1 08:16
本帖最后由 pokerbean 于 2010-12-1 08:17 编辑

如果不在乎输赢对称，应该是乘以比2小，比1大的一个数，但是具体是多少我也说不清。

Howard 发表于 2010-12-1 06:42

你说的很对，其实你上面说的F（4，2）也是这种情况：
按我的公式（按考虑特定队的输赢定义）F（4,2）=8，而如你所说的14减半，则应该是7；可是你如果去数“4场比赛A队至少连输2场的情况”，确实是8种，所以F(n,m)公式本身在算单方面时没错（至少现在还没错）；麻烦出在最后不能简单乘2，问题其实是出在AABB与BBAA这两种情况被统计了两次，也就是你说，“A连输2场”和“B连输2场”不是互斥的。

作者: 沙天马士 时间: 2010-12-1 09:10
本帖最后由沙天马士于 2010-12-1 10:02 编辑

思路是这样。。大家拍砖吧。

assume 10 coin flip. 我们不能有3 个以上连续。。分母是2^10 , 我们要算 ...
windstormm 发表于 2010-12-1 06:27

发现问题了，问题出在-2，第一个-2没问题，第二个-2也没问题，第三个就应该-4了。。。。。第一个-2是8个样本-2，剩下6个样本，乘以2后市12个样本，这时同正或同反得样本还是2个，用12-2，剩下10个样本，10乘以2是20个样本，这20个样本同正或同反的就是4个样本，需要-4，然后下一轮我算了下需要-6,减得这些数是关于k的函数，减掉的数之和就是出现连续k次同面的组合数
所以用那个式子做simulation的时候，n和k的差较小的时候公式出现不了问题，n和k的差大的时候就远远偏离正确值了

作者: Howard 时间: 2010-12-2 01:46
本帖最后由 Howard 于 2010-12-2 04:24 编辑

这道题的确超乎我目前知识水平。在网上找到了正确答案，果然需要用递归。只不过我还是不理解这个答案是怎么算出来的。

以下是我翻译的答案：

n次掷硬币中不出现k个连续正面的概率是 [attach]894[/attach]

其中 [attach]895[/attach]代表Fibonacci k-step number（k阶斐波那契数列中第L个数）

所以老墙的题若是修改一下，变成238场不出现巴萨5连输的概率是多少？应该先找到5阶斐波那契数列，再找出其第240 (238+2)个数，这个数就是所有出现巴萨5连输的所有组合，拿这个数除以总组合数2^238，就可以了。

n阶斐波那契数列定义如下：

1）当k<=0时，[attach]896[/attach]

2) 当k=1, k=2时，[attach]897[/attach]

3）当k>2时，[attach]898[/attach]

来源：
1）n阶斐波那契数列: http://mathworld.wolfram.com/Fibonaccin-StepNumber.html
2) Run: http://mathworld.wolfram.com/Run.html

作者: Howard 时间: 2010-12-2 01:54
我们平常所提的斐波那契数列其实是2阶的，也就是说，数列里面每一个数都是前面2个数的和。

n阶斐波那契数列，每一个数都是前面n个数的和。

作者: windstormm 时间: 2010-12-2 02:03

发现问题了，问题出在-2，第一个-2没问题，第二个-2也没问题，第三个就应该-4了。。。。。第一个-2是8个 ...
沙天马士发表于 2010-12-1 09:10

你这样改一改，应该可以得出howard 找到的答案，

其实如今computing power 那么大，最简单就是做simulation.. 1mil run of 238 coin flips. 数一数有几个没有5 个以上输赢就行了。。就几行code ，结果可以非常精确。。

作者: Howard 时间: 2010-12-2 02:04
本帖最后由 Howard 于 2010-12-2 04:22 编辑

用 Excel 计算了一下，5阶斐波那契数列的第240个数是7.84241E+69，除以2的238次方（4.4171E+71），结果是1.775%

中间结论：
巴萨和皇马水平绝对平均，每场比赛都分出胜负，238场比赛中巴萨不出现5连输的概率是1.775%，皇马不出现5连输的概率也是1.775%。至于皇马和巴萨都不出现5连输的概率，还是不知道。

作者: Howard 时间: 2010-12-2 04:29

你说的很对，其实你上面说的F（4，2）也是这种情况：
按我的公式（按考虑特定队的输赢定义）F（4,2）=8，而如你所说的14减半，则应该是7；可是你如果去数“4场比赛A队至少连输2场的情况”，确实是 8种，所以F(n,m)公式本身在算单方面时没错（至少现在还没错）；麻烦出在最后不能简单乘2，问题其实是出在AABB与BBAA这两种情况被统计了两次，也就是你说，“A连输2场”和“B连输2场”不是互斥的。
pokerbean 发表于 2010-12-1 08:16

照这样看来，你的F（n,m)递归公式也是不对滴，虽然这绝对是可行的思路。正确的公式里面每一项F(n, m)应该由m个F(i, m) 相加而来，i的值从n-1到n-i。

作者: Howard 时间: 2010-12-2 07:01
这道题简直太神了，看似很简单，其实复杂程度超乎想象。而且迄今为止在网上没有找到确切答案。我计划从两连败开始研究一下，慢慢推广到5连败。呼吁高人加入讨论

作者: bedok 时间: 2010-12-2 09:39
本帖最后由 bedok 于 2010-12-2 09:47 编辑

太纠结了呵呵

作者: muyir 时间: 2010-12-2 14:37
为什么搞这么复杂了
假设只有输赢，没有平局
第一场结果定了后
第二场和第一场同的概率是1/2
..
第五场和第一场同的概率是1/2
所以，连赢/输5场概率是1/16，也就是约3%
不会出现这种情况的概率是97%

实际上足球比赛会有平局
那么第一场出现输赢的概率是2/3
第二场和第一场同的概率是1/3
..
第五场和第一场同的概率是1/3
所以，连赢/输5场概率是2/243，也就是约0.8%
不会出现这种情况的概率是99.2%

作者: muyir 时间: 2010-12-2 14:44
如果限定238场，就是第二种情况出现也不稀奇阿，好比一个人对你胜率是1%，比100场，他应该会赢1次的
是我想得太简单了么？

作者: 沙天马士 时间: 2010-12-2 19:42

你这样改一改，应该可以得出howard 找到的答案，

其实如今computing power 那么大，最简单就是做simulat ...
windstormm 发表于 2010-12-2 02:03

恩，大家只是想一般性解决此类问题，2 2 4 6貌似还就是那个数列的二阶形式

作者: 沙天马士 时间: 2010-12-2 19:48
这个题对研究扑克波动和资金管理有一点帮助，比如打多少场SNG中连续损失多少buyin的概率

作者: pokerbean 时间: 2010-12-2 20:43

照这样看来，你的F（n,m)递归公式也是不对滴，虽然这绝对是可行的思路。正确的公式里面每一项F(n, m ...
Howard 发表于 2010-12-2 04:29

嗯，既然知道不出现的概率分子是M阶Fibonacci，你这么说也许是对的。

不过我验算了到F(12,5)的，好象还没发现错误。

作者: pokerbean 时间: 2010-12-2 20:51

这道题简直太神了，看似很简单，其实复杂程度超乎想象。而且迄今为止在网上没有找到确切答案。我计划从两连 ...
Howard 发表于 2010-12-2 07:01

二连不难啊，不计输赢的情况下，就是你前面说的，只有“ABAB……”和“BABA……”两种捣乱分子，所以：

P（n,2）=(2^n-2)/(2^n);

三连就麻烦点，因为不但要排除ABAB……和BABA……；
还要排除AABAAB……和BBABBA……；
还要排除上面两种链条的组合拼接；

四连就要排除前面三种情况的组合拼接……，M阶Fib数应该就是那么掺和进来的。

还得说墙厉害啊，随便抛出个问题，让这些人忙乎这么半天，他自己倒躲一边偷着乐去了。

作者: Howard 时间: 2010-12-2 21:22

为什么搞这么复杂了
假设只有输赢，没有平局
第一场结果定了后
第二场和第一场同的概率是1/2
..
第五场和第 ...
muyir 发表于 2010-12-2 14:37

muyir兄，你说的是前5场比赛（或者指定5场比赛），出现5连输的概率，而题目要求的是238场中任意位置至少出现1次5连输。

而且还不能把238场比赛看作1-5，2-6，3-7，。。。直到234-238 等234个“连续5场”的实验，因为他们不是独立事件。

作者: Howard 时间: 2010-12-2 21:25

二连不难啊，不计输赢的情况下，就是你前面说的，只有“ABAB……”和“BABA……”两种捣乱分子，所以 ...
pokerbean 发表于 2010-12-2 20:51

不错，二连“不计输赢”反而比“计较输赢”要简单的多，因为总数减2就可以。

但是二连“计较输赢”怎么算呢？当然现在公式是知道了，就是 Fib(n+2)/2^n。但是我还是没搞懂这是怎么得到的。

作者: Howard 时间: 2010-12-2 23:38
归根到最简单，最基本的问题，谁能帮我解释一下。

抛质地均匀的硬币n次，硬币两面为A面和B面，问：A面无任何连续出现的概率是多少？也即，每次如果出现A面，它前后必须是B面。

已知结果是Fib(n+2)/2^n，其中Fib（k）表示Fibonacci数列的第k个数。现在的问题是，知道结果了，还是不知道推理过程。谁能帮我给出一个合理的推导？

作者: 伟大的墙 时间: 2010-12-3 13:30
回复 51# Howard

我知道风暴是搞概率统计的
看这回贴觉得豆子和老霍也是搞这个的

作者: bedok 时间: 2010-12-3 15:47
根据Howard的算法我演算了几个例子，看来是正确的。
我现在也想知道这个算法的推导过程，感觉到它的简约的美，但是却理解不了，真是痛苦。
如果推导都出不来，那研究“两个队都不连输”就更是找不到灵感了啊（假设是可以用类似的方法解决的）。

作者: 哪吒 时间: 2010-12-3 22:14
X 不成立

作者: Howard 时间: 2010-12-3 22:30

根据Howard的算法我演算了几个例子，看来是正确的。
我现在也想知道这个算法的推导过程，感觉到它的简约的 ...
bedok 发表于 2010-12-3 15:47

我想知道推导过程的原因，正是想从此得知“两个队都不出现连输”的算法。

作者: Howard 时间: 2010-12-3 22:36
上次得到了“中间结论”：
巴萨和皇马水平绝对平均，每场比赛都分出胜负，238场比赛中巴萨不出现5连输的概率是1.775%，皇马不出现5连输的概率也是1.775%。

两队都不出现5连输的概率，还是不知道。但可以估算。比赛场次越少，“巴萨不出现5连输”和“皇马不出现5连输”的关联越大；而比赛场次越多，这两个事件就越接近于独立事件。238场足够大，我认为可以近似看作独立事件。所以，巴萨和皇马均不出现两连输的概率近似于1.775%*1.775% = 0.0315%

作者: pokerbean 时间: 2010-12-3 23:43

我想知道推导过程的原因，正是想从此得知“两个队都不出现连输”的算法。 ...
Howard 发表于 2010-12-3 22:30

这么分析行不行：

假设我们把连比N场的那个分子叫做K(n)，为叙述方便我们说它代表的是不连输；

然后我们把连比N+1场的情况看成（比一场，再比N场）
第一场的情况要么赢，要么输；
I。赢的情况下，对有效情况组合没有影响，就是看后面N场的，是K(n)；
II。输的情况下，就要分两种情况：
　　1。接下来的N场的第一场输了，这一半就全不用考虑了（0）；
　　2。接下来的N场的第一场赢了，那就要看后面N-1场的，即K(n-1)

所以K(n+1)=K(n)+K(n-1),这个Fib关系已经在了，

然后考虑边界条件，K(n)只有在n>=2的时候才有效，所以最终结果是Fib数列平移两位，即K(n)=Fib(n+2)。

作者: Howard 时间: 2010-12-4 00:01

这么分析行不行：

假设我们把连比N场的那个分子叫做K(n)，为叙述方便我们说它代表的是不连输；

然 ...
pokerbean 发表于 2010-12-3 23:43

赞！应该是正解。只是有一点我还有疑虑，也是我走入歧途的原因。

n+1场可以看作先比1场，再比n场，这是方式1。同时也可以看作先比n场，再加一场，这是方式2。怎样证明方式1完全涵盖方式2，且没有多出的，没有遗漏的？也就是说，怎样证明方式1和方式2是等价的？从结果来看，一定是等价的。但我当时老想着，这1场既可以放到开头，也可以放到结尾，所以就老有个2×在公式里面。

作者: Howard 时间: 2010-12-4 00:04

赞！应该是正解。只是有一点我还有疑虑，也是我走入歧途的原因。

n+1场可以看作先比1场，再比n场， ...
Howard 发表于 2010-12-4 00:01

想明白了，方式1和2等价。可以用反证。因为1和2的对称关系，不妨假设方式1比方式2多出若干种组合。

则在方式1多出的组合里面，所有n+1场都没有两连输，因此前面n场当然也没有两连输，应该同时也被划归方式2。故此两者完全等价。

作者: runyutong 时间: 2010-12-4 00:56

归根到最简单，最基本的问题，谁能帮我解释一下。

抛质地均匀的硬币n次，硬币两面为A面和B面，问：A面无任 ...
Howard 发表于 2010-12-2 23:38

这个结果不是1/2^(n-1)，不连续不只有ABABAB…，BABABA…，两种可能吗？

作者: 沙天马士 时间: 2010-12-4 02:11
回复 60# runyutong
A面不连续，B面可以连续

作者: Howard 时间: 2010-12-5 05:37
本帖最后由 Howard 于 2010-12-5 05:38 编辑

赞！应该是正解。只是有一点我还有疑虑，也是我走入歧途的原因。

n+1场可以看作先比1场，再比n场， ...
Howard 发表于 2010-12-4 00:01

昨天去打扑克的时候就一直在想这个问题，突然发现我的“歧途“其实也不那么歧。

我当时是这么想的，假设n场没有两连输是K(n), 那么K（n+1）可以看作先比1场，再比n场。

I。若这n场中的第一场（总第二场）输，则先比的第一场必是胜，剩下的组合数就是K（n-2）。为什么不是K（n-1）呢？因为n场中第一场输，第二场必然是胜，从第三场开始才随便排列。

II。若这n场中第一场胜，则先比的第一场随便，可以胜也可以输，n场中从第二场开始也就是K（n-1），所以总共是2×K（n-1）

综合I和II，可得K（n+1）=2K（n-1）+ K（n-2）

然后我就郁闷了，因为这跟标准答案不一致。标准答案是菲薄拿起数列，也就是K（n+1）=K（n）+ K（n-1）。从我的答案怎么也推算不出标准的答案。

昨天又发现，虽然从我的推不出标准，但是从标准可以推出我的。因为菲薄拿起数列的定义，
K（n+1）=K（n）+ K（n-1）（1）
K（n）=K（n-1）+ K（n-2）（2）

（2）代入（1）即可得到: K（n+1）=2K（n-1）+ K（n-2），也就是我的答案！

然后我就想，菲薄拿起数列可以推导出我的，那我的也可以反推回去。但是经过3个小时的努力，我发现我完全找不到办法推回去！

总结一下我的疑问：如何证明K（n+1）=2K（n-1）+ K（n-2）其实就是菲薄拿起数列K（n+1）=K（n）+ K（n-1）???

作者: Howard 时间: 2010-12-5 14:28
不出现3连输的情况，假设n场是K（n）种组合，计算n+1场，可以看作先比1场，再比n场。

一。如果这一场输了，那么要求后面n场中的第一场：
I。赢，可以，剩下n-1场，也就是K（n-1）
II。输，分情况
1. n场中前两场是输输，这就没得玩了，三连输出现。0
2. n场中前两场是输赢，剩下的n-2场任意，就是K（n-2）

二。如果这一场赢了，剩下n场任意，也就是K（n）

综上，K（n+1）= K（n）+ K（n-1）+ K（n-2），也就是3阶菲薄拿起数列。

作者: damajer 时间: 2010-12-5 19:37
不知道这题有没有被解开，简单想了下，推出了递推公式，但求出通项公式比较麻烦。先给出解法：

我们可以把双方的战绩简化成以下描述方式：巴萨连胜X场，然后皇马连胜X场，然后巴萨X场，然后皇马X场。。。（X在1-4之间，当然一开始也可能是皇马-巴萨-皇马-。。。）。然后我们可以来构造一种双方n场比赛的战绩排列可能：先把所有n场有序比赛任意分成若干个部分，每个部分的长度为1-4，然后，把奇数部分写成巴萨胜，偶数写成皇马胜，或者奇数写成皇马胜，偶数写成巴萨胜。可见，要罗列n场对战（小于5场连胜或连败）的所有可能性，即等价于求出把n个有序单位分成若干部分（每部分长度1-4）的所有可能性的2倍。

我们设Pn为n个单位能够分成若干部分（每部分长度1-4）的所有可能分法数。先分析n个单位的分法：分出1个单位，然后对n-1个单位进行分割；分出2个单位，然后对n-2个单位进行分割；分出3个单位，然后对n-3个单位进行分割；分出4个单位，然后对n-4个单位进行分割。

所以，我们得出递推公式：

Pn=P(n-1)+P(n-2)+P(n-3)+P(n-4)

所求概率为（2×Pn）/2^n

n=238带入即原题答案。

这个公式求解起来很麻烦，首先要凑出 Pn-aP(n-1)-bP(n-2)-cP(n-3)=s[P(n-1)-aP(n-2)-bP(n-3)-cP(n-4)] 的形式，累加得出Pn关于P(n-1),P(n-2),P(n-3)的递推公式，然后继续凑数累加消项得出Pn关于P(n-1),P(n-2)的递推公式，接着重复求出Pn关于P(n-1)的公式，最后求出Pn的通项公式。。。本人就不求了。期待达人求出结果。。。

作者: damajer 时间: 2010-12-5 19:38
再把公式改得完美一点：

两队n场比赛不出现m场连胜或连败的可能性为：2*p(n,m)/2^n

其中p(n,m)=p(n-1,m)+p(n-2,m)+...+p(n-m+1,m)

当m=3时，p(n,3)为斐波那契数列。

原题为m=5的情况，通项公式待求。。。

作者: Howard 时间: 2010-12-6 10:30

再把公式改得完美一点：

两队n场比赛不出现m场连胜或连败的可能性为：2*p(n,m)/2^n

其中p(n,m)=p(n-1,m)+ ...
damajer 发表于 2010-12-5 19:38

赞一个先！思路独特，清晰简洁，我暂时没发现任何不对劲的地方。

帮忙看一下我62楼的问题如何？

作者: Howard 时间: 2010-12-6 11:03
本帖最后由 Howard 于 2010-12-7 00:15 编辑

再把公式改得完美一点：

两队n场比赛不出现m场连胜或连败的可能性为：2*p(n,m)/2^n

其中p(n,m)=p(n-1,m)+p(n-2,m)+...+p(n-m+1,m)

当m=3时，p(n,3)为斐波那契数列。

原题为m=5的情况，通项公式待求。。。
damajer 发表于 2010-12-5 19:38

从最初始的几场算了一下，确定了一下初始条件。

n场巴萨不出现3连输概率是 F3(n+2)/2^n, 其中F3(n+2)表示3阶斐波那契数列的第n+2个数；
n场任一队均不出现3连输概率是2×F2(n+1)/2^n，其中F2(n+1）表示 2阶斐波那契数列（也就是普通斐波那契数列）的第n+1个数；

n场巴萨不出现4连输概率是 F4(n+2)/2^n, 其中F4(n+2)表示4阶斐波那契数列的第n+2个数；
n场任一队均不出现4连输概率是2×F3(n+1)/2^n，其中F3(n+1）表示 3阶斐波那契数列的第n+1个数；

n场巴萨不出现5连输概率是 F5(n+2)/2^n, 其中F5(n+2)表示5阶斐波那契数列的第n+2个数；
n场任一队均不出现5连输概率是2×F4(n+1)/2^n，其中F4(n+1）表示 4阶斐波那契数列的第n+1个数；

n场巴萨不出现m连输概率是 Fm(n+2)/2^n, 其中Fm(n+2)表示m阶斐波那契数列的第n+2个数；
n场任一队均不出现m连输概率是2×F[m-1](n+1)/2^n，其中F[m-1](n+1）表示 m-1阶斐波那契数列的第n+1个数；

回到墙的问题，238场任意一队不出现5连输：
n=238时，F4（n+1）= F4(239) = 3.84651E+67
2×F4(n+1)/2^n = 2*3.84651E+67 / 4.41712E+71 = 0.0174%

终于算出来了！

---附：m阶斐波那契数列的第k个数定义如下-------

1）当k<=0时，Fm(k)=0;

2) 当k=1, k=2时，Fm(1)=Fm(2)=1;

3）当k>2时，Fm(k)=Fm(k-1) + Fm(k-2) + ... + Fm(k-m)

作者: taoljj 时间: 2010-12-6 11:11

本帖最后由 Howard 于 2010-12-5 05:38 编辑

总结一下我的疑问：如何证明K（n+1）=2K（n-1）+ K（n-2）其实就是菲薄拿起数列K（n+1）=K（n）+ K（n-1）???
Howard 发表于 2010-12-5 05:37

被一个笑话引了过来，一早上都在看这个了。

要证明Howard的公式就是斐波那契数列其实可以用个简单的方法-枚举法：
因为根据题意得知：K（2）= 3 ，K（3） = 5，K（4） = 8，带入公式可枚举出的数列就是斐波那契数列，不知howard认可否？

作者: Howard 时间: 2010-12-6 11:21

被一个笑话引了过来，一早上都在看这个了。

要证明Howard的公式就是斐波那契数列其实可以用个简单的方法 ...
taoljj 发表于 2010-12-6 11:11

枚举可以证伪，只要有一个不符合就足够了；但无法证实，因为就算枚举到100000时都没问题，难保下一个就有问题。有点像哥德巴赫猜想，算到10^10000000了都吻合，但是仍然无法证明，呵呵。我那个公式推到斐波那契数列可能很简单一步就能过去，但是我卡壳了就是想不到。

作者: damajer 时间: 2010-12-6 17:21

赞一个先！思路独特，清晰简洁，我暂时没发现任何不对劲的地方。

帮忙看一下我62楼的问题如何？ ...
Howard 发表于 2010-12-6 10:30

对于K（n+1）=2K（n-1）+ K（n-2）就是斐波那契数列的证法，其一可以用数学归纳法，也是最简单的方法，证法略；另外也可以纯用数学方法推导，证法如下：

我们先把原公式写成K(n+1)-aK(n)-bK(n-1)=s[K(n)-aK(n-1)-bK(n-2)]的形式，然后列出所有项：

K(n+1)-aK(n)-bK(n-1)=s[K(n)-aK(n-1)-bK(n-2)]
K(n)-aK(n-1)-bK(n-2)=s[K(n-1)-aK(n-2)-bK(n-3)]
K(n-1)-aK(n-2)-bK(n-3)=s[K(n-2)-aK(n-3)-bK(n-4)]
...
K(4)-aK(3)-bK(2)=s[K(3)-aK(2)-bK(1)]

以上各项左右相乘消项，得：

K(n+1)-aK(n)-bK(n-1)=s^(n-2)[K(3)-aK(2)-bK(1)]

由K(3)=2,K(2)=1,K(1)=1,代入得：

K(n+1)-aK(n)-bK(n-1)=s^(n-2)(2-a-b)

然后我们要解出s、a、b的值。由原式我们可列出一个方程组：

a+s=0
b-as=2
-bs=1

注意这里可能会有多个解，但我们只需要其中一个解就够了。我们可以用投机取巧的方法：假设a=1，b=1是原式的解（因为如果a=b=1是该式解的话对于我们来说将更方便地得出结论），代入解出原式的一个解为：s=-1，a=1，b=1。代入我们刚刚解出的方程，即得到斐波那契的递推公式：

K(n+1)=K(n)+bK(n-1)

作者: enenppl 时间: 2010-12-6 19:31
为什么要算这样的题呢?

作者: Howard 时间: 2010-12-7 00:31

对于K（n+1）=2K（n-1）+ K（n-2）就是斐波那契数列的证法，其一可以用数学归纳法，也是最简单的方法， ...
damajer 发表于 2010-12-6 17:21

唉，差距太大了，这个证明的思路，我自己再琢磨1年也想不出来。

作者: Howard 时间: 2010-12-7 00:33

为什么要算这样的题呢?
enenppl 发表于 2010-12-6 19:31

因为我觉得算出这道题来的愉悦感效应超过花在这道题的时间上的机会成本。你得承认有些人就是这样，他被一个东西迷住以后不弄出来简直就是日思夜想。

欢迎光临智游城 (http://zhiyoucheng.co/)