抛硬币次数的期望

数学

---

网上遇到的一个面试题：反复抛一枚硬币，直到抛出两次正面为止。我们期望要抛多少次？（默认这个硬币正反面的概率都是0.5）

想了半天这个问题，后来又遇到两种类型的抛硬币问题：

• 反复抛一枚硬币，直到抛出$k$次正面为止，求次数的期望
• 反复抛一枚硬币，直到出现连续$k$次正面为止，求次数的期望

两种问题唯一的区别就是连续不连续，首先看下不连续的情况

不连续 - 解法1

$k=2$，直接计算级数

假设一共抛了$n$次，则最后一次为正面，前$n-1$次有一次正面，则次数的概率为

$$p(n) = \frac{1}{2}\cdot \binom{n-1}{1}\left(\frac{1}{2}\right)\left(\frac{1}{2}\right)^{n-2} = (n-1)\left(\frac{1}{2}\right)^n$$
则次数的期望为
$$E = \sum_{n=1}^{+\infty} n\cdot p(n) = \sum_{n=1}^{+\infty}n(n-1)\left(\frac{1}{2}\right)^n$$

现在转换为求解该级数的问题，两种方法求解该级数问题，一是错位相减大法，另一个是积分-求和-求导

错位相减

$$\begin{align*} S & = \frac{1(1-1)}{2^1} + \frac{2(2-1)}{2^2} + \cdots + \frac{n(n-1)}{2^n} \\ \frac{1}{2} S & = \frac{1(1-1)}{2^2} + \frac{2(2-1)}{2^3} + \cdots + \frac{(n-1)(n-2)}{2^n} + \frac{n(n-1)}{2^{n+1}} \end{align*}$$
两式相减得，
$$\begin{align*} \frac{1}{2} S & = \frac{0}{2^1} + \frac{2\times 1 - 1\times 0}{2^2} + \frac{3\times2-2\times1}{2^3} + \cdots + \frac{n(n-1)-(n-1)(n-2)}{2^n} - \frac{n(n-1)}{2^{n+1}} \\ & = \frac{0}{2^1} + \frac{2}{2^2} + \frac{4}{2^3} + \cdots + \frac{2(n-1)}{2^n} - \frac{n(n-1)}{2^{n+1}} \\ & = 0 + \frac{1}{2^1} + \frac{2}{2^2} + \cdots + \frac{n-1}{2^{n-1}} - \frac{n(n-1)}{2^{n+1}} \end{align*}$$
让
$$\begin{align*} T & = \frac{1}{2^1} + \frac{2}{2^2} + \frac{3}{2^3} + \cdots + \frac{n-1}{2^{n-1}} \\ \frac{1}{2}T & = \frac{1}{2^2} + \frac{2}{2^3} + \frac{3}{2^4} + \cdots + \frac{n-2}{2^{n-1}} + \frac{n-1}{2^n} \\ \frac{1}{2}T & = \frac{1}{2^1} + \frac{1}{2^2} + \cdots + \frac{1}{2^{n-1}} - \frac{n-1}{2^n} \\ & = 1 - \frac{1}{2^{n-1}} - \frac{n-1}{2^n} \\ T & = 2 \end{align*}$$

则，$S=2T=4$，次数的期望$E=4$，这次就不用考虑从几开始的问题了

积分-求和-求导

错位相减无法得到更通用的解，这里采用积分-求和-求导的方法求解，并把其扩展到通用的$k$次

这种方法是本科高数求无穷级数的方法，设$f(x) = n(n-1)x^n$，要求

$$\begin{align*} S & = \sum_{n=1}^{+\infty}n(n-1)\left(\frac{1}{2}\right)^n \\ & = \sum_{n=1}^{+\infty}f(\frac{1}{2}) \end{align*}$$
现在需要把$f$中的$n(n-1)$消掉，采用的方法为积分，设
$$\begin{align*} G(x) & = x^n \\ g(x) & = G''(x) \\ & = n(n-1)x^{n-2} \\ f(x) & = x^2g(x) \\ & = x^2G''(x) \end{align*}$$
级数求和变为
$$\begin{align*} S(x) & = \sum_{n=1}^{+\infty}f(x) \\ & = \sum_{n=1}^{+\infty}x^2G''(x) \\ & = x^2\sum_{n=1}^{+\infty}G''(x) \\ & = x^2\left(\sum_{n=1}^{+\infty}x^n\right)'' \\ & = x^2\left( \frac{x-x^{n+1}}{1-x} \right)'' \\ & = x^2\left(\frac{x}{1-x}\right)'' \\ & = x^2 \cdot \frac{2}{(1-x)^3} \\ & = \frac{2x^2}{(1-x)^3} \\ S(\frac{1}{2}) & = 4 \end{align*}$$
故期望次数为$4$

现在来扩展到$k$次，设次数为$n$，正面的概率为$x$，则前$n-1$次有$k-1$次正面

$$\begin{align*} p(n) & =x\cdot \binom{n-1}{k-1}x^{k-1} (1-x)^{n-k} \\ & = \binom{n-1}{k-1}x^k(1-x)^{n-k} \end{align*}$$
期望为
$$\begin{align*} E & = \sum_{n=1}^{+\infty}np(n) \\ & = \sum_{n=1}^{+\infty}n \binom{n-1}{k-1}x^k(1-x)^{n-k} \end{align*}$$

设

$$\begin{align*} f(x) & = n\binom{n-1}{k-1} x^k(1-x)^{n-k} \\ & = \frac{n(n-1)(n-2)\cdots(n-k+1)}{(k-1)!}x^k(1-x)^{n-k} \end{align*}$$
为了计算方便设反面的概率为$\hat{x} = 1-x$
约到式子前面的含$n$项
$$\begin{align*} G(\hat{x}) & = \hat{x}^n \\ g(\hat{x}) & = G^{(k)}(\hat{x}) \\ & = n(n-1)\cdots (n-k+1)\hat{x}^{n-k} \\ f(x) & = \frac{(1-\hat{x})^k}{(k-1)!}g(\hat{x}) \\ & = \frac{(1-\hat{x})^k}{(k-1)!}G^{(k)}(\hat{x}) \end{align*}$$
级数求和变为
$$\begin{align*} S & = \sum_{n=1}^{+\infty}f(\hat{x}) \\ & = \sum_{n=1}^{+\infty}\frac{(1-\hat{x})^k}{(k-1)!}G^{(k)}(\hat{x}) \\ & = \frac{(1-\hat{x})^k}{(k-1)!}\sum_{n=1}^{+\infty}G^{(k)}(\hat{x}) \\ & = \frac{(1-\hat{x})^k}{(k-1)!}\left(\sum_{n=1}^{+\infty}\hat{x}^n\right)^{(k)} \\ & = \frac{(1-\hat{x})^k}{(k-1)!}\left(\frac{\hat{x}}{1-\hat{x}}\right)^{(k)} \\ & = \frac{(1-\hat{x})^k}{(k-1)!}\left( \frac{1}{(1-\hat{x})^2} \right)^{(k-1)} \\ & = \frac{(1-\hat{x})^k}{(k-1)!}\left( \frac{1}{(\hat{x}-1)^2} \right)^{(k-1)} \\ & = \frac{(1-\hat{x})^k}{(k-1)!}\cdot (-1)^{(k-1)}k!(\hat{x}-1)^{-(k+1)} \\ & = \frac{(1-\hat{x})^k}{(k-1)!}\cdot (-1)^{(k-1)}k!(1-\hat{x})^{-(k+1)}(-1)^{-(k+1)} \\ & = \frac{(1-\hat{x})^k}{(k-1)!}\cdot k!(1-\hat{x})^{-(k+1)} \\ & = \frac{k(1-\hat{x})^k}{(1-\hat{x})^{k+1}} \\ & = \frac{k}{1-\hat{x}} \\ & = \frac{k}{x} \end{align*}$$
所以当硬币均匀的时候的通项为
$$E(\frac{1}{2}) = 2k$$

不连续 - 解法2

解法2非常简单，把不连续的$k$次正面分解成$k$个小过程：

抛一次硬币第一次出现正面停止，所抛的次数为事件$X_1$，则不连续的$k$次正面被分解成了，连续发生$k$次事件$X_1$，所以

$$X = kX_1$$
所以期望为 $$E[X] = kE[X_1] = 2k$$

---

连续

对于连续的情况比不连续要复杂一点，网上给出了一个过程分解的思路：

设连续抛出$k$次正面的次数为$T_k$，则得到$k$次正面的过程可以分解为：首先已经得到了连续$k-1$次正面的情况，所用次数为$T_{k-1}$，再抛一次，如果得到正面则游戏结束（还需要$0.5\times0$次），如果得到反面，则游戏重新开始（还需要$0.5\times T_k$次），递推公式如下

$$\begin{align*} T_k & = T_{k-1} + 1 + 0.5\times 0 + 0.5 \times T_k \\ T_k & = 2T_{k-1} + 2 \end{align*}$$

那么只需要计算出$T_1$就可以了，$T_1$可以看成抛$n$次硬币，前$n-1$次为反面，最后一次为正面

$$p(n)=\left(\frac{1}{2}\right)^n$$
$$\begin{align*} E & = \sum_{n=1}^{+\infty}np(n) \\ & = \sum_{n=1}^{+\infty}n\left(\frac{1}{2}\right)^n \\ & = 2-\frac{1}{2^{n-1}} - \frac{n}{2^n} \quad //错位相减 \\ & = 2 \end{align*}$$

很容易求出$T_k$的通项

$$\begin{align*} T_k & = 2T_{k-1}+2 \\ & = 2(2T_{k-1}+2)+2 \\ & = 2^{k-1}T_1 + 2^1+2^2+2^3+\cdots+2^{k-1} \\ & = 2^{k-1}T_1 + 2^k-2 \\ & = 2^{k-1}(2+T_1) - 2 \\ & = 2^{k+1} - 2 \\ \end{align*}$$

---

过程分解的方法相当于换了一种思路去考虑问题，连续的情况怎么用基本事件的方式求解还没弄明白

强行又复习了一遍高数 >.<

正面概率为$x$时的，一次正面结束的期望次数

这时

$$p(n) = x(1-x)^{n-1}$$
为了计算方便，反面概率为$\hat{x}=1-x$
$$p(n) = (1-\hat{x})\hat{x}^{n-1}$$

期望为

$$\begin{align*} E & = \sum_{n=1}^{+\infty} n(1-\hat{x})\hat{x}^{n-1} \\ & = (1-\hat{x})\sum_{n=1}^{+\infty}n\hat{x}^{n-1} \\ & = (1-\hat{x}) \sum_{n=1}^{+\infty} \left( \hat{x}^n \right)' \\ & = (1-\hat{x}) \left(\sum_{n=1}^{+\infty} \hat{x}^n \right)' \\ & = (1-\hat{x})\left(\frac{\hat{x}}{1-\hat{x}} \right)' \\ & = (1-\hat{x}) \frac{1}{(1-\hat{x})^2} \\ & = \frac{1}{1-\hat{x}} \\ & = \frac{1}{x} \end{align*}$$

所以

• 不连续$k$，$E = \frac{k}{x}$
• 连续$k$，$E = 2^{k-1}(2+\frac{1}{x})-2$

---

2018-08-26 更新

上述方法的思路也可用于求解一次正面结束的期望次数，假设正面的概率为$p$，并且所求期望为$S$，则按照上面的思路，假设已经抛了若干次均是反面，则该次如果抛得正面（概率为$p$），则该过程停止，还需要的次数为$0$次；而如果该次抛得反面（概率为$1-p$），则该过程相当于重新开始（因为每次实验都是相互独立的，如果把其当做一个序列，不管从那一刻起，其得到一次正面结束的期望次数均相同，均等于$S$），故在整个过程看来，有如下等式成立

$$S = 1 + p\cdot 0 + (1-p) \cdot S \\ S = \frac{1}{p}$$

Reference

有道概率题：一个有趣的抛硬币问题
抛硬币直到出现连续N次正面为止的期望