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 the table is empty, starting with 3 fair coins.

Let $N$ be the number of coins on the table at the beginning of a round.
Initially, $N_0 = 3$.
In each round, every coin currently on the table is flipped.
A coin is removed if it lands tails (T).
A coin stays if it lands heads (H).
The game ends when the number of coins on the table is 0.
We want to find $\mathbb{E}[R]$.

Let $X_i$ be the number of coins remaining after round $i$, given that there were $N_{i-1}$ coins before round $i$.
The process stops when $X_i = 0$.
Let $R$ be the number of rounds. $R = \min \{k : X_k = 0\}$.
Actually, the problem says "The game ends at the moment the table is empty".
So if we start with $N$ coins, we flip them. Some stay, some go.
Let $S$ be the number of coins that stay. $S$ follows a Binomial distribution $B(N, 1/2)$.
If $S=0$, the game ends after 1 round.
If $S > 0$, we continue with $S$ coins.

Let $E_n$ be the expected number of additional rounds needed to empty the table given that there are currently $n$ coins on the table.
We want to find $E_3$.
The base case is $E_0 = 0$.
For $n \ge 1$, in the next round, we flip $n$ coins.
Each coin has probability $1/2$ of staying and $1/2$ of being removed.
Let $k$ be the number of coins that stay. $k$ can range from $0$ to $n$.
The probability that exactly $k$ coins stay is $\binom{n}{k} (1/2)^n$.
If $k=0$, the game ends, so we used 1 round.
If $k > 0$, we used 1 round and then need $E_k$ more rounds.
So, the recurrence relation is:
$E_n = 1 + \sum_{k=0}^n P(k \text{ coins stay}) \cdot (\text{expected additional rounds})$
Wait, if $k=0$, additional rounds is 0. If $k>0$, it is $E_k$.
So,
$E_n = 1 + \sum_{k=1}^n \binom{n}{k} (1/2)^n E_k$
$E_n = 1 + \frac{1}{2^n} \sum_{k=1}^n \binom{n}{k} E_k$

Let's check for small values of $n$.
$E_0 = 0$.

For $n=1$:
$E_1 = 1 + \frac{1}{2^1} \binom{1}{1} E_1$
$E_1 = 1 + \frac{1}{2} E_1$
$\frac{1}{2} E_1 = 1 \implies E_1 = 2$.
Let's verify.
Start with 1 coin.
Round 1:
- H (prob 1/2): coin stays. We are back to state 1.
- T (prob 1/2): coin removed. State 0. Game ends.
Let $R$ be the number of rounds.
$P(R=1) = 1/2$.
$P(R=2) = (1/2)(1/2) = 1/4$.
$P(R=k) = (1/2)^k$.
$\mathbb{E}[R] = \sum_{k=1}^\infty k (1/2)^k = 2$. Correct.

For $n=2$:
$E_2 = 1 + \frac{1}{4} \left[ \binom{2}{1} E_1 + \binom{2}{2} E_2 \right]$
$E_2 = 1 + \frac{1}{4} [ 2(2) + 1(E_2) ]$
$E_2 = 1 + \frac{1}{4} [ 4 + E_2 ]$
$E_2 = 1 + 1 + \frac{1}{4} E_2$
$E_2 = 2 + \frac{1}{4} E_2$
$\frac{3}{4} E_2 = 2$
$E_2 = \frac{8}{3}$.

For $n=3$:
$E_3 = 1 + \frac{1}{8} \left[ \binom{3}{1} E_1 + \binom{3}{2} E_2 + \binom{3}{3} E_3 \right]$
We know $E_1 = 2$ and $E_2 = 8/3$.
$E_3 = 1 + \frac{1}{8} \left[ 3(2) + 3(8/3) + 1(E_3) \right]$
$E_3 = 1 + \frac{1}{8} \left[ 6 + 8 + E_3 \right]$
$E_3 = 1 + \frac{1}{8} [ 14 + E_3 ]$
$E_3 = 1 + \frac{14}{8} + \frac{1}{8} E_3$
$E_3 = 1 + \frac{7}{4} + \frac{1}{8} E_3$
$E_3 = \frac{11}{4} + \frac{1}{8} E_3$
$\frac{7}{8} E_3 = \frac{11}{4}$
$E_3 = \frac{11}{4} \cdot \frac{8}{7}$
$E_3 = \frac{11 \cdot 2}{7} = \frac{22}{7}$.

Let's double check the calculations.
Recurrence: $E_n = 1 + \frac{1}{2^n} \sum_{k=1}^n \binom{n}{k} E_k$.
This can be rewritten as $E_n (1 - \frac{1}{2^n}) = 1 + \frac{1}{2^n} \sum_{k=1}^{n-1} \binom{n}{k} E_k$.
$E_n \frac{2^n - 1}{2^n} = 1 + \frac{1}{2^n} \sum_{k=1}^{n-1} \binom{n}{k} E_k$.
$E_n (2^n - 1) = 2^n + \sum_{k=1}^{n-1} \binom{n}{k} E_k$.

Let's re-calculate $E_1, E_2, E_3$.
$n=1$:
$E_1 (2^1 - 1) = 2^1 + \sum_{k=1}^{0} ...$ (empty sum is 0)
$E_1 (1) = 2 \implies E_1 = 2$. Correct.

$n=2$:
$E_2 (3) = 4 + \binom{2}{1} E_1 = 4 + 2(2) = 8$.
$E_2 = 8/3$. Correct.

$n=3$:
$E_3 (7) = 8 + \binom{3}{1} E_1 + \binom{3}{2} E_2$
$E_3 (7) = 8 + 3(2) + 3(8/3)$
$E_3 (7) = 8 + 6 + 8 = 22$.
$E_3 = 22/7$. Correct.

Is there a general formula?
Let's check $n=4$.
$E_4 (15) = 16 + \binom{4}{1} E_1 + \binom{4}{2} E_2 + \binom{4}{3} E_3$
$E_4 (15) = 16 + 4(2) + 6(8/3) + 4(22/7)$
$E_4 (15) = 16 + 8 + 16 + \fra