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.
Initially, there are $n=3$ coins.
In each round, every coin currently on the table is flipped.
If a coin lands heads, it stays.
If a coin lands tails, it is removed.
The game ends when there are 0 coins left.
The coins are fair, so $P(H) = P(T) = 1/2$.

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$, since if there are 0 coins, the game is already over.

Let's analyze the transition from $n$ coins to $k$ coins.
Suppose we have $n$ coins. We flip all of them.
Each coin lands heads with probability $1/2$ and tails with probability $1/2$.
The number of coins remaining, say $K$, follows a binomial distribution $B(n, 1/2)$.
So, $P(K=k) = \binom{n}{k} (1/2)^n$ for $k = 0, 1, \dots, n$.
After this round, we have $k$ coins. The number of rounds played so far is 1.
The expected total rounds starting from $n$ coins is $1 + \sum_{k=0}^n P(K=k) E_k$.
So, $E_n = 1 + \sum_{k=0}^n \binom{n}{k} \frac{1}{2^n} E_k$.
Note that $E_0 = 0$.
So, $E_n = 1 + \frac{1}{2^n} \sum_{k=1}^n \binom{n}{k} E_k$.

Let's compute $E_1, E_2, E_3$ step by step.

Case $n=1$:
$E_1 = 1 + \frac{1}{2^1} \sum_{k=1}^1 \binom{1}{k} E_k$
$E_1 = 1 + \frac{1}{2} \binom{1}{1} E_1$
$E_1 = 1 + \frac{1}{2} E_1$
$E_1 - \frac{1}{2} E_1 = 1$
$\frac{1}{2} E_1 = 1 \implies E_1 = 2$.
This makes sense. With 1 coin, we flip it.
If T (prob 1/2), game ends (1 round).
If H (prob 1/2), we have 1 coin again, so we need $1 + E_1$ rounds.
$E_1 = \frac{1}{2}(1) + \frac{1}{2}(1 + E_1) = 1 + \frac{1}{2}E_1 \implies E_1 = 2$.

Case $n=2$:
$E_2 = 1 + \frac{1}{2^2} \sum_{k=1}^2 \binom{2}{k} E_k$
$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 E_1 + 1 E_2 ]$
We know $E_1 = 2$.
$E_2 = 1 + \frac{1}{4} [ 2(2) + 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$
$E_2 - \frac{1}{4} E_2 = 2$
$\frac{3}{4} E_2 = 2$
$E_2 = \frac{8}{3}$.

Case $n=3$:
$E_3 = 1 + \frac{1}{2^3} \sum_{k=1}^3 \binom{3}{k} E_k$
$E_3 = 1 + \frac{1}{8} \left[ \binom{3}{1} E_1 + \binom{3}{2} E_2 + \binom{3}{3} E_3 \right]$
$E_3 = 1 + \frac{1}{8} [ 3 E_1 + 3 E_2 + 1 E_3 ]$
Substitute $E_1 = 2$ and $E_2 = 8/3$.
$E_3 = 1 + \frac{1}{8} [ 3(2) + 3(8/3) + E_3 ]$
$E_3 = 1 + \frac{1}{8} [ 6 + 8 + E_3 ]$
$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{4}{4} + \frac{7}{4} + \frac{1}{8} E_3$
$E_3 = \frac{11}{4} + \frac{1}{8} E_3$
$E_3 - \frac{1}{8} E_3 = \frac{11}{4}$
$\frac{7}{8} E_3 = \frac{11}{4}$
$E_3 = \frac{11}{4} \times \frac{8}{7}$
$E_3 = \frac{11 \times 2}{7}$
$E_3 = \frac{22}{7}$.

Let's double check the logic.
Is there a general formula?
Let $E_n$ be the expected number of rounds.
$E_n = 1 + \frac{1}{2^n} \sum_{k=0}^n \binom{n}{k} E_k$
$E_n = 1 + \frac{1}{2^n} \sum_{k=1}^n \binom{n}{k} E_k$
$2^n E_n = 2^n + \sum_{k=1}^n \binom{n}{k} E_k$
$2^n E_n - \binom{n}{n} E_n = 2^n + \sum_{k=1}^{n-1} \binom{n}{k} E_k$
$(2^n - 1) E_n = 2^n + \sum_{k=1}^{n-1} \binom{n}{k} E_k$
$E_n = \frac{2^n + \sum_{k=1}^{n-1} \binom{n}{k} E_k}{2^n - 1}$

Let's re-calculate using this formula.
$n=1$:
$E_1 = \frac{2^1 + 0}{2^1 - 1} = \frac{2}{1} = 2$. Correct.

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

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

Let's check $n=4$ just to see if there is a pattern or if I made a silly arithmetic error.
$E_4 = \frac{2^4 + \binom{4}{1} E_1 + \binom{4}{2} E_2 + \binom{4}{3} E_3}{2^4 - 1}$
$E_4 = \frac{16 + 4(2) + 6(8/3) + 4(22/7)}{15}$
$E_4 = \frac{16 + 8 + 16 + 88/7}{15}$
$E_4 = \frac{40 + 88/7}{15} = \frac{280/7 + 88/7}{15} = \frac{368/