How to slove it,3

假设有一个硬币，抛出字（背面）和花（正面）的概率都是0.5，而且每次抛硬币与前次结果无关。
现在做一个游戏，连续地抛这个硬币，直到连续出现两次字为止，问平均要抛多少次才能结束游戏？
注意，一旦连续抛出两个“字”向上游戏就结束了，不用继续抛。


另外一个变形是，硬币铸造时有差错，抛出字和花的概率分别是p和1-p （0<=p<=1），问平均要抛多少次才能结束这个游戏。 设 字为A 花为B， 把抛出来的结果写成字符串， 现在求 *不连续* 构成两个A 的字符串组合数。 用向量 [A B] 表示 [尾为A的组合数 尾为B的组合数]， 因为A后面只能接B，而B后面可以接A或B，所以状态转移矩阵 M 是 0 1 1 1 一次结果：A、B [A1 B1] = [1 1] 两次结果：AB、BA、 BB [A2 B2] = M*[A1 B1] = = [1 2] 三次结果： [A3 B3] = M*[A2 B2] = = [2 3] 四次结果： [A4 B4] = M*[A3 B3] = [3 5] A1，A2，A3....An 这个数列的意义是，抛n 次，得到*非终止*序列的 而且最后一次为 A 的组合数。 只要在这些组合后面再抛一次 A 即可得到终止序列。 从上面可以看出 An 正是斐波那契数 F(n)，可以直接代入通项公式。 所以抛 n 次得到终止序列的概率为 F(n-1)/2^n 得到终止序列的抛硬币次数期望为：2*F(1)/2^2 + 3*F(2)/2^3 + 4*F(3)/2^4 + ....

A_n是斐波那契数有组合意义, 只要讨论前两个次试验的情况, 如果第一次是B, 后面构成A_(n-1)结构, 如果第一次是A, 则第二次必须是B, 于是后面构成A_(n-2)结构, 于是在考察一下A_1和A_2就可以了.

对于期望的计算, 可以考虑生成函数.

设
G(x) = F(1)/2^2 * x^2 + F(2)/2^3 * x^3 + F(3)/2^4 * x^4 + ...
将递归关系带入得到
G(x) = x/(4-2x-x^2)

于是那个无限求和的期望就等于 G'(1)=4. 注意这个期望是最后两次A之前的试验次数, 故加上最后两次A就是期望6了.