math-prob-01

# The Vanishing Coins

You start with **3 fair coins** on the table.

A **round** consists of flipping every coin that is currently on the table (all at once). After the flips, remove every coin that landed **tails**; every coin that landed **heads** stays on the table for the next round. You then play another round with whatever coins remain.

The game ends at the moment the table is empty (no coins remain).

Let $R$ be the number of rounds played until the table is empty. Compute the expected value $\mathbb{E}[R]$.

Give your answer as an exact fraction in lowest terms, written as `a/b` (for example, `7/3`).

The problem asks for the expected number of rounds $R$ until all 3 coins are removed from the table. Let $X_i$ be the number of rounds coin $i$ stays on the table. The game ends when the last coin is removed, so $R = \max(X_1, X_2, X_3)$.

For a single fair coin, it is removed in round $k$ if it lands heads $k-1$ times and then tails. The probability of this is $(1/2)^{k-1} \cdot (1/2) = (1/2)^k$. Thus, $X_i$ follows a geometric distribution with parameter $p=1/2$ (supported on $\{1, 2, 3, \dots\}$).

We want to compute $\mathbb{E}[R] = \mathbb{E}[\max(X_1, X_2, X_3)]$.
Using the tail sum formula for expectation, $\mathbb{E}[R] = \sum_{k=1}^{\infty} P(R \ge k)$.
The event $R \ge k$ is equivalent to $\max(X_1, X_2, X_3) \ge k$, which means at least one coin remains on the table after round $k-1$ (or is removed in round $k$ or later).
It is easier to compute the complement: $P(R < k) = P(\max(X_1, X_2, X_3) < k) = P(X_1 < k, X_2 < k, X_3 < k)$.
Since the coins are independent, $P(R < k) = [P(X_1 < k)]^3$.
$P(X_1 < k) = P(X_1 \le k-1) = \sum_{j=1}^{k-1} (1/2)^j = 1 - (1/2)^{k-1}$.
So, $P(R \ge k) = 1 - [1 - (1/2)^{k-1}]^3$.

Now we sum this probability:
$$ \mathbb{E}[R] = \sum_{k=1}^{\infty} \left( 1 - \left( 1 - \frac{1}{2^{k-1}} \right)^3 \right) $$
Let $j = k-1$. The sum becomes:
$$ \mathbb{E}[R] = \sum_{j=0}^{\infty} \left( 1 - \left( 1 - \frac{1}{2^j} \right)^3 \right) $$
For $j=0$, the term is $1 - (1-1)^3 = 1$.
For $j \ge 1$, we expand $(1 - x)^3 = 1 - 3x + 3x^2 - x^3$ with $x = 1/2^j$:
$$ 1 - \left( 1 - \frac{3}{2^j} + \frac{3}{4^j} - \frac{1}{8^j} \right) = \frac{3}{2^j} - \frac{3}{4^j} + \frac{1}{8^j} $$
So,
$$ \mathbb{E}[R] = 1 + \sum_{j=1}^{\infty} \left( \frac{3}{2^j} - \frac{3}{4^j} + \frac{1}{8^j} \right) $$
We evaluate the geometric series:
$$ \sum_{j=1}^{\infty} \frac{1}{2^j} = 1, \quad \sum_{j=1}^{\infty} \frac{1}{4^j} = \frac{1/4}{1-1/4} = \frac{1}{3}, \quad \sum_{j=1}^{\infty} \frac{1}{8^j} = \frac{1/8}{1-1/8} = \frac{1}{7} $$
Substituting these values:
$$ \mathbb{E}[R] = 1 + 3(1) - 3\left(\frac{1}{3}\right) + 1\left(\frac{1}{7}\right) $$
$$ \mathbb{E}[R] = 1 + 3 - 1 + \frac{1}{7} = 3 + \frac{1}{7} = \frac{22}{7} $$

Alternatively, using the recurrence relation $E_n = 1 + \sum_{k=0}^n \binom{n}{k} (1/2)^n E_k$ with $E_0=0$:
$E_1 = 2$
$E_2 = 8/3$
$E_3 = 22/7$

The fraction $22/7$ is in lowest terms.

\boxed{22/7}