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`).

We are given a stochastic process:

- Start with **3 fair coins**.
- In each round:
  - Flip all current coins.
  - Remove all that land **tails**.
  - Keep all that land **heads**.
- Repeat until no coins remain.

Let $ R $ be the number of rounds played until the table is empty.

We are to compute $ \mathbb{E}[R] $.

---

### Key Observations

Each coin behaves independently: each round, a coin either survives (if it lands heads) or is removed (if tails). So each coin has a geometric-like survival process: it stays as long as it keeps getting heads.

But the game ends when **all** coins have been removed — i.e., when the **last** coin finally gets a tail.

So if we let $ T_i $ be the number of rounds coin $ i $ survives (i.e., number of consecutive heads before first tail), then $ T_i \sim \text{Geometric}(p = 1/2) $, where we define geometric as counting the number of trials **until first failure**, i.e., support $ \{1, 2, 3, \dots\} $, with $ \mathbb{P}(T_i = k) = (1/2)^k $ (since need $ k-1 $ heads then a tail), and expectation $ \mathbb{E}[T_i] = 2 $.

But the game ends at round $ R = \max(T_1, T_2, T_3) $, because the last coin to be removed determines when the table becomes empty.

So we need:

$$
\mathbb{E}[R] = \mathbb{E}[\max(T_1, T_2, T_3)]
$$

where $ T_1, T_2, T_3 $ are i.i.d. geometric with success probability $ 1/2 $ (failure = tail), support $ \{1,2,3,\dots\} $.

Let’s compute this expectation.

---

### Distribution of Maximum of i.i.d. Geometric Variables

Let $ M = \max(T_1, T_2, T_3) $. For integer $ k \ge 1 $:

$$
\mathbb{P}(M \le k) = \mathbb{P}(T_1 \le k, T_2 \le k, T_3 \le k) = [\mathbb{P}(T_1 \le k)]^3
$$

Now compute $ \mathbb{P}(T_1 \le k) $. Since $ T_1 $ is number of trials until first tail (including the tail), then:

$$
\mathbb{P}(T_1 > k) = \mathbb{P}(\text{first } k \text{ flips are all heads}) = \left(\frac{1}{2}\right)^k
$$

So:

$$
\mathbb{P}(T_1 \le k) = 1 - \left(\frac{1}{2}\right)^k
$$

Hence:

$$
\mathbb{P}(M \le k) = \left(1 - \frac{1}{2^k}\right)^3
$$

Then the survival function:

$$
\mathbb{P}(M > k) = 1 - \left(1 - \frac{1}{2^k}\right)^3
$$

We can compute expectation via:

$$
\mathbb{E}[M] = \sum_{k=0}^\infty \mathbb{P}(M > k)
$$

But careful: since $ M \ge 1 $, we can use:

$$
\mathbb{E}[M] = \sum_{k=1}^\infty \mathbb{P}(M \ge k) = \sum_{k=0}^\infty \mathbb{P}(M > k)
$$

Yes, both are equivalent.

So:

$$
\mathbb{E}[R] = \sum_{k=0}^\infty \left[1 - \left(1 - \frac{1}{2^k}\right)^3\right]
$$

But note: for $ k = 0 $, $ \frac{1}{2^0} = 1 $, so $ 1 - (1 - 1)^3 = 1 - 0 = 1 $. So term is 1.

Let’s compute:

$$
\mathbb{E}[R] = \sum_{k=0}^\infty \left[1 - \left(1 - \frac{1}{2^k}\right)^3\right]
= \sum_{k=0}^\infty \left[1 - \left(1 - \frac{3}{2^k} + \frac{3}{4^k} - \frac{1}{8^k}\right)\right]
$$

Wait: expand $ (1 - x)^3 = 1 - 3x + 3x^2 - x^3 $. Here $ x = \frac{1}{2^k} $, so:

$$
\left(1 - \frac{1}{2^k}\right)^3 = 1 - \frac{3}{2^k} + \frac{3}{4^k} - \frac{1}{8^k}
$$

Thus:

$$
1 - \left(1 - \frac{1}{2^k}\right)^3 = \frac{3}{2^k} - \frac{3}{4^k} + \frac{1}{8^k}
$$

So:

$$
\mathbb{E}[R] = \sum_{k=0}^\infty \left( \frac{3}{2^k} - \frac{3}{4^k} + \frac{1}{8^k} \right)
$$

Now compute each sum separately.

Recall geometric series: $ \sum_{k=0}^\infty r^k = \frac{1}{1 - r} $ for $ |r| < 1 $. So:

- $ \sum_{k=0}^\infty \frac{1}{2^k} = \frac{1}{1 - 1/2} = 2 $
- $ \sum_{k=0}^\infty \frac{1}{4^k} = \frac{1}{1 - 1/4} = \frac{4}{3} $
- $ \sum_{k=0}^\infty \frac{1}{8^k} = \frac{1}{1 - 1/8} = \frac{8}{7} $

So:

$$
\mathbb{E}[R] = 3 \cdot 2 - 3 \cdot \frac{4}{3} + \frac{8}{7}
= 6 - 4 + \frac{8}{7}
= 2 + \frac{8}{7}
= \frac{14}{7} + \frac{8}{7}
= \frac{22}{7}
$$

Wait — is this correct? Let's double-check.

Hold on: The geometric distribution we used has support $ \{1,2,3,\dots\} $, and $ \mathbb{P}(T > k) = (1/2)^k $ for $ k \ge 0 $. So yes, $ \mathbb{P}(T > 0) = 1 $, $ \mathbb{P}(T > 1) = 1/2 $, etc.

Then:

$$
\mathbb{E}[T] = \sum_{k=0}^\infty \mathbb{P}(T > k) = \sum_{k=0}^\infty \left(\frac{1}{2