令random number X为number of tosses to get m consecutive heads。令random number Y为number of tosses to get m-1 consecutive heads。

下面求解 E(X|Y=y)

x=y+1时， P(X=y+1|Y=y) = 1/2
x>y+1时， P(X=x|Y=y) = 1/2 * (x-y-1)

所以 E(X|Y=y) = 1/2 * (y+1) + 1/2 * ((y+1) + E(X)) = y + 1 + E(X)/2

所以 E(E(X|Y=y)) = E(y + 1 + E(X)) = E(Y) + 1 + E(X)/2

我们知道 E(X) = E(E(X|Y=y)), 即 E(X) = E(Y) + 1 + E(X)/2 => E(X) = 2 (E(Y) + 1)

所以 E(X) = 2^(m-1) * (E(Y_m=1) + 2) - 2

其中 random number Y_m=1 为 number of tosses to get 1 consecutive head， E(Y_m=1) = 1/p = 2

所以 E(X) = 2^(m+1) - 2


至于第二题，思路上并不难，只是结果不好解也不好表达。

-*
+-*
...
+++++++-*
++++++++*

P(n) = P(n-1)/2 + P(n-2)/4 + ... + P(n-m)/2^m + 1/2^m

令 f(n) = 2^n * (P(n) - 1)

f(n) = f(n-1) + f(n-2) + ... + f(n-m) 当k<m时， f(k) = -2^k

m=1时 f(n)是常数数列

m=2时 f(n)是斐波那契数列

...

一般的f(n)可以用矩阵表示

令 G = (m*m matrix)

0 1 0 0 ... 0
0 0 1 0 ... 0
0 0 0 1 ... 0
...
0 0 0 0 ... 1
1 1 1 1 ... 1


令 L = (1*m vector)

0 0 0 ... 0 1

令 V = (m*1 vector)


1
2
4
...
2^(m-1)

当k>=m时，f(n)可以表示为: f(n) = -L * G^(n-m+1) * V

P(n) = f(n) * 2^(-n) + 1