Table of Contents
题目
不断抛一枚公平硬币。平均要抛多少次，才会第一次出现连续\(5\)次正面？
分析
设\(E_k\)表示“当前已经连续出现了\(k\)个正面（\(k=0,1,2,3,4\)）时，到首次出现连续\(5\)个正面还需要的期望抛掷次数”。显然\(E_5=0\)。
对\(k=0,1,2,3,4\)，下一次抛掷会发生两种情况：
- 以\(\frac{1}{2}\)概率出正面，状态变成\(k+1\)；
- 以\(\frac{1}{2}\)概率出反面，连续正面被打断，状态回到\(0\)。
因此有递推
\[ E_k=1+\frac{1}{2}E_{k+1}+\frac{1}{2}E_0\]
从后往前写：
\[ \begin{aligned} E_4&=1+\frac{1}{2}E_0\\ E_3&=1+\frac{1}{2}E_4+\frac{1}{2}E_0=\frac{3}{2}+\frac{3}{4}E_0\\ E_2&=1+\frac{1}{2}E_3+\frac{1}{2}E_0=\frac{7}{4}+\frac{7}{8}E_0\\ E_1&=1+\frac{1}{2}E_2+\frac{1}{2}E_0=\frac{15}{8}+\frac{15}{16}E_0 \end{aligned}\]
再代回\(k=0\)式子：
\[ \begin{aligned} E_0&=1+\frac{1}{2}E_1+\frac{1}{2}E_0\\ \frac{1}{2}E_0&=1+\frac{1}{2}\left(\frac{15}{8}+\frac{15}{16}E_0\right)\\ \frac{1}{2}E_0&=\frac{31}{16}+\frac{15}{32}E_0\\ \frac{1}{32}E_0&=\frac{31}{16} \end{aligned}\]
通项公式（目标为连续\(n\)个正面）
把上面的\(5\)推广成一般\(n\)。定义\(E_k\)为“当前连续正面数为\(k\)时，到首次达到连续\(n\)个正面还需的期望次数”，则\(E_n=0\)，并满足
\[ E_k=1+\frac{1}{2}E_{k+1}+\frac{1}{2}E_0\quad(k=0,1,\dots,n-1).\]
令\(D_k=E_k-E_{k+1}\)，两式相减可得
\[ D_k=\frac{1}{2}D_{k+1}\quad(k=0,1,\dots,n-2),\]
因此\(D_k=2^{n-1-k}D_{n-1}\)。又由
\[ E_{n-1}=1+\frac{1}{2}E_0\]
可得\(D_{n-1}=E_{n-1}-E_n=1+\frac{1}{2}E_0\)，于是
\[ E_0=\sum_{k=0}^{n-1}D_k=(2^n-1)\left(1+\frac{1}{2}E_0\right).\]
解得
\[ E_0=2^{n+1}-2.\]
更一般地，
\[ E_k=2^{n+1}-2^{k+1}\quad(k=0,1,\dots,n).\]
所以
\[ E_0=62\]
也就是说，平均要抛\(62\)次，才会第一次出现连续\(5\)个正面。