一道纯概率题

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

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

bean还有一句话我仔细琢磨也觉得有点问题

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

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

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

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

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

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

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

如果不在乎输赢对称，应该是乘以比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场”不是互斥的。

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

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的差大的时候就远远偏离正确值了

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

以下是我翻译的答案：

n次掷硬币中不出现k个连续正面的概率是

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

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

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

1） 当k<=0时，

2) 当k=1, k=2时，

3） 当k>2时，

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

我们平常所提的斐波那契数列其实是2阶的，也就是说，数列里面每一个数都是前面2个数的和。

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

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

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

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

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

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

    你说的很对，其实你上面说的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。