出现连续 $r$ 个正面时,抛硬币的次数的期望

hbghlyj

Hw8Sol.pdf
Problem 33
不断抛掷一枚正面朝上概率为 $p$ 的硬币。计算在出现连续 $r$ 个正面之时的抛掷次数的期望。
令 $X$ 为在出现连续 $r$ 个正面之时的次数, $Y$ 表示在第一次出现反面之时的次数。则$$E[X]=E[E[X \mid Y]]=\sum_{i=1}^{\infty} E[X \mid Y=i] P\{Y=i\}$$
注意到 $P\{Y=i\}=p^{i-1}(1-p)$. 若 $i \leq r$, 则这个反面使前 $i-1$ 次正面都白费了, 重新从第 $i+1$ 次抛掷开始算, 在出现连续 $r$ 个正面之时的次数, 于是$E[X \mid Y=i]=i+E[X]$. 若 $i>r$, 则前 $r$ 次都是正面, 于是 $E[X \mid Y=i]=r$. 式子变为
\begin{aligned}
E[X] &=\sum_{i=1}^{\infty} E[X \mid Y=i] P\{Y=i\} \\
&=(1-p) \sum_{i=1}^r p^{i-1}(i+E[X])+(1-p) \sum_{i=r+1}^{\infty} p^{i-1} r \\
&=(1-p)\left(\sum_{i=1}^r i p^{i-1}\right)+E[X](1-p)\left(\sum_{i=1}^r p^{i-1}\right)+r p^r \\
&=(1-p)\left(\sum_{i=1}^r i p^{i-1}\right)+E[X]\left(1-p^r\right)+r p^r
\end{aligned}我们计算
\begin{aligned}
\sum_{i=1}^r i p^{i-1} &=\sum_{i=1}^{\infty} i p^{i-1}-\sum_{i=r+1}^{\infty} i p^{i-1} \\
&=\frac{1}{(1-p)^2}-\sum_{i=r+1}^{\infty} r p^{i-1}-\sum_{i=r+1}^{\infty}(i-r) p^{i-1} \\
&=\frac{1}{(1-p)^2}-\frac{r p^r}{1-p}-\sum_{i=1}^{\infty} i p^{r+i-1} \\
&=\frac{1}{(1-p)^2}-\frac{r p^r}{1-p}-\frac{p^r}{(1-p)^2} \\
&=\frac{1-(1-p) r p^r-p^r}{(1-p)^2}
\end{aligned}故\begin{aligned}
E[X]&=(1-p)\left(\sum_{i=1}^r i p^{i-1}\right)+E[X]\left(1-p^r\right)+r p^r \\
&=(1-p)\left(\frac{1-(1-p) r p^r-p^r}{(1-p)^2}\right)+E[X]\left(1-p^r\right)+r p^r \\
&=\frac{1-p^r}{1-p}+E[X]\left(1-p^r\right) .
\end{aligned}解出 $E[X]$, 得
\[
E[X]=\frac{1-p^r}{p^r(1-p)} .
\]

hbghlyj

Problem 34
For another approach to Theoretical Exercise 33, let $T_r$ denote the number of flips required to obtain a run of $r$ consecutive heads.
(a) Determine $E\left[T_r \mid T_{r-1}\right]$.
Let $j$ be an integer with $j \geq r-1$. Let $I=1$ if the $j+1$ flip is heads and $I=0$ if it is tails. Then
$E\left[T_r \mid T_{r-1}=j\right]=E\left[T_r \mid T_{r-1}=j, I=0\right] P\{I=0\}+E\left[T_r \mid T_{r-1}=j, I=1\right] P\{I=1\}$.
If $I=0$, that is the next flip is tails, we start over trying to get $r$ consecutive heads. Thus $E\left[T_r \mid T_{r-1}=j, I=0\right]=j+1+E\left[T_r\right]$. If $I=1$, then we've succeeded at getting $r$ consecutive heads, and so $E\left[T_r \mid T_{r-1}=j, I=1\right]=j+1$. Hence
\[
\begin{aligned}
E\left[T_r \mid T_{r-1}=j\right] &=E\left[T_r \mid T_{r-1}=j, I=0\right] P\{I=0\}+E\left[T_r \mid T_{r-1}=j, I=1\right] P\{I=1\} \\
&=\left(j+1+E\left[T_r\right]\right)(1-p)+(j+1) p \\
&=j+1+(1-p) E\left[T_r\right]
\end{aligned}
\]
That is, $E\left[T_r \mid T_{r-1}\right]$ is the function of $T_{r-1}$ whose value at $T_{r-1}=j$ is
\[
j+1+(1-p) E\left[T_r\right]
\]
(b) Determine $E\left[T_r\right]$ in terms of $E\left[T_{r-1}\right]$.
We have
\[
\begin{aligned}
E\left[T_r\right] &=E\left[E\left[T_r \mid T_{r-1}\right]\right] \\
&=\sum_j E\left[T_r \mid T_{r-1}=j\right] P\left\{T_{r-1}=j\right\} \\
&=\sum_j\left(j+1+(1-p) E\left[T_r\right]\right) P\left\{T_{r-1}=j\right\} \\
&=\left(\sum_j j \cdot P\left\{T_{r-1}=j\right\}\right)+1+(1-p) E\left[T_r\right] \\
&=E\left[T_{r-1}\right]+1+(1-p) E\left[T_r\right]
\end{aligned}
\]
Hence
\[
E\left[T_r\right]=\frac{E\left[T_{r-1}\right]}{p}+\frac{1}{p} .
\]
(c) What is $E\left[T_1\right]$ ?
\[
E\left[T_1\right]=\sum_{i=1}^{\infty} i P\left\{T_1=i\right\}=\sum_{i=1}^{\infty} i(1-p)^{i-1} p=\frac{p}{p^2}=\frac{1}{p}
\]
since $\sum_{n=1}^{\infty} n x^{n-1}=\frac{1}{(1-x)^2}$ for $|x|<1$.
(d) What is $E\left[T_r\right]$ ?
\[
\begin{aligned}
E\left[T_r\right] &=\frac{E\left[T_{r-1}\right]}{p}+\frac{1}{p} \\
&=\frac{E\left[T_{r-2}\right]}{p^2}+\frac{1}{p^2}+\frac{1}{p} \\
&=\ldots \\
&=\frac{E\left[T_1\right]}{p^{r-1}}+\sum_{i=1}^{r-1} \frac{1}{p^i} \\
&=\frac{1}{p^r}+\frac{p^{-1}-p^{-r}}{1-p^{-1}} \\
&=\frac{p^r-1}{p^r(p-1)}
\end{aligned}
\]