一道纯概率题

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

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

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

回复 51# Howard


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

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

X      不成立

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

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

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

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

我想知道推导过程的原因，正是想从此得知“两个队都不出现连输”的算法。 ...
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)。

这么分析行不行：

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

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

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

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

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

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

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

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

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

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

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