一道有意思的题目

题目是这样说的：

连续掷一个质地均匀的硬币，直到第一次出现连续两次正面为止。问恰好掷n次的概率是多少。

先看样本空间——可能出现的情况有哪些。

• 掷1次，2种情况
• 掷2次，2*2种情况
• ...
• 掷n次，2^n中情况

再来看看目标事件包含哪些情况，我们用1表示正面，0表示反面

• 至少需要掷两次，有(1，1)
• 掷三次，有(0，1，1)
• 掷四次，有(0，0，1，1)、(1，0，1，1)
• 掷五次，有(0，0，0，1，1)、(1，0，0，1，1)、(0，1，0，1，1)
• ......

一开始，我到这里就卡住了。开始求助万能的网友，网友贴出了参考答案。

用f(x)表示恰好掷x次，第一次出现连续两个正面的个数，且第一次掷出反面；
用g(x)表示恰好掷x次，第一次出现连续两个正面的个数，且第一次掷出正面。则：
f(1) = 0, g(1) = 0
f(2) = 0, g(2) = 1
当x>=3时，
f(x+1) = f(x) + g(x)，
g(x+1) = f(x)
解释如下，当第一次是反面，下一次正面反面都可以，因此有f(x+1) = f(x) + g(x)，类似的，当第一次是正面，下一次必须是反面才可以，因此有g(x+1)= f(x)
由此，得出f(x+2) = f(x+1) + f(x)，也就是符合斐波那契数列的关系，求出f(x)，也就能求出g(x)，二者求和就是掷n次恰好第一次出现连续两个正面的所有情况

答案讲得很有道理，但是关键的推导步骤难说通，为什么第一次是反面，下一次下一次既可以是正面也可以是反面。

左思右想，我给这个答案想了一个解释。

• 当x= 1, 2时是没有疑义的
• 当x>=3时，采用倒推法来思考。
  • 无论如何，最后三次的结果是确定的——(0，1，1)，那么可以想象成每次都是往第一位添加一个数字(0或1)
  • f(x+1)的意思是掷x+1次，第1次必须是反面，首次出现连续2个正面的次数。那在前x次中，
    • 第1次是反面的情况里，在前面添加1个反面
    • 第1次是正面的情况里，在前面添加1个反面
    • 这样可以有 f(x+1) = f(x) + g(x)
  • 类似的，g(x+1)只能在第一次是反面的情况里，在前面添加1个正面得到，所以有g(x+1) = f(x)

举例来说，考虑x = 4的情况：
会出现如下结果：
第一次是反面： (0，0，1，1)
第一次是正面： (1，0，1，1)
即 f(4) = 1, g(4) = 1
x + 1 = 5，则有如下结果：
第一次为反面： (0，0，0，1，1)、(0，1，0，1，1)
第一次为正面： (1，0，0，1，1)

随手草图

由此可以很好地解释递推公式。

当然，斐波那契的通项公式，需要用另外的方法求解，以后再聊……