硬币配对 V

设 $e_i$ 为当前有 $i$ 个正面时，到达 4 个正面还需要的期望动作次数（每次操作算 2 个动作）。

$e_4=0$。

• $i=3$：选 1 个反面 + 1 个正面。翻反面使其变正，重掷另一枚正面：以 $1/2$ 回到 3 个正面，以 $1/2$ 到 4 个正面。

$$e_3=2+\frac12 e_3+\frac12 e_4\Rightarrow e_3=4.$$

• $i=2$：选两枚反面。翻其中一枚变正，重掷另一枚反面：以 $1/2$ 到 4 个正面、以 $1/2$ 到 3 个正面。

$$e_2=2+\frac12 e_4+\frac12 e_3=4.$$

• $i=1$：选两枚反面。翻一枚变正，重掷另一枚：以 $1/2$ 到 3 个正面、以 $1/2$ 到 2 个正面。

$$e_1=2+\frac12 e_3+\frac12 e_2=6.$$

• $i=0$：选两枚反面。翻一枚变正，重掷另一枚：以 $1/2$ 到 2 个正面、以 $1/2$ 到 1 个正面。

$$e_0=2+\frac12 e_2+\frac12 e_1=7.$$

初始正面数 $X\sim\mathrm{Binomial}(4,1/2)$，因此期望动作数为

$$\mathbb{E}[e_X]=\frac{71}{16}=4.4375.$$

---

Original Explanation

Let $T$ be the total number of coin flips needed and $X$ be the total number of heads that appear on the first flipping of the coins. Then $\mathbb{E}[T] = \mathbb{E}[\mathbb{E}[T \mid X]] = \sum_{k=0}^{4}\mathbb{E}[T \mid X =k]\mathbb{P}[X = k]$ by Law of Total Expectation. $X \sim \text{Binom}\left(4,\dfrac{1}{2}\right)$ because $X$ counts the number of heads appearing in $4$ flips of a fair coin. To set our notation, let $e_i$ represent the additional number of flips needed to stop our process once we have $i$ heads.

If $X = 4$, then we get 4 heads, so $\mathbb{E}[T \mid X = 4] = 4$. This would mean $e_4 = 0$.

If $X = 3$, then we would consider one heads and one tails. We should turn over the tails so that we have a guaranteed head, i.e., we end up with either $3$ or $4$ heads after this process. Then, with equal probability, we would get a heads or tails on the remaining coin, so $e_3 = 2 + \dfrac{1}{2}e_3 + \dfrac{1}{2}e_4$. Putting in $e_4 = 0$ yields $e_3 = 4$. This means $\mathbb{E}[T \mid X = 3] = 8$.

If $X = 2$, then we are considering $2$ tails, meaning we turn one over and flip the other. This is exactly the same scenario as above as we are guaranteed to have $3$ or $4$ heads after with the same probabilities, so $e_2 = 4$ as well. This means $\mathbb{E}[T \mid X = 2] = 8$.

If $X = 1$, then we consider $2$ tails. We turn one over, and then we flip the other. We will end with either $2$ or $3$ heads after this iteration with equal probability. Therefore, $e_1 = 2 + \dfrac{1}{2}e_2 + \dfrac{1}{2}e_3$. As $e_2 = e_3 = 4$, $e_1 = 6$. This means $\mathbb{E}[T \mid X = 1] = 10$.

Lastly, if $X = 0$, we just consider $2$ tails again. We turn one over, and then we flip the other. We will end with either $1$ or $2$ heads after this iteration with equal probability, so $e_0 = 2 + \dfrac{1}{2}e_1 + \dfrac{1}{2}e_2$. Plugging in $e_1 = 6$ and $e_2 = 4$ yields $e_0 = 7$, so $\mathbb{E}[T \mid X = 0] = 11$.

Finally, we can plug the values and the PMF of $X$ into our expression from the beginning, we get that $\mathbb{E}[T] = \dfrac{1}{16} \cdot 4 + \dfrac{4}{16} \cdot 8 + \dfrac{6}{16} \cdot 8 + \dfrac{4}{16} \cdot 10 + \dfrac{1}{16} \cdot 11 = \dfrac{135}{16}$.