Answer: The Collector's Rival: Who Finishes First?

Key Idea / Intuition

Alice needs to complete all $n = 4$ types — this is the classical coupon collector problem, with expected waiting time $4(1 + 1/2 + 1/3 + 1/4) = 4 \cdot \frac{25}{12} \approx 8.33$ days. Bob only needs 2 specific types out of 4, which sounds much easier. The surprise is in how much easier: Bob's problem reduces to waiting for both type-1 and type-2 to appear, which is a simple inclusion-exclusion calculation — and it finishes far faster on average. Let's find the probability that Bob finishes before Alice.

The key technique is to compute the distribution of finishing times for each player and compare, or more elegantly, compute $P(\text{Bob finishes} \leq k)$ vs $P(\text{Alice finishes} \leq k)$ and find who is more likely to finish first.

---

Formal Proof / Solution

Step 1: Bob's finishing time.

Bob needs both type 1 and type 2 to appear. Each day, the coupon is type 1 with probability $1/4$, type 2 with probability $1/4$, and "other" with probability $1/2$.

Let $T_B$ = first time both type 1 and type 2 have appeared. By inclusion-exclusion:

$P(T_B > k) = P(\text{no type 1 in } k \text{ days}) + P(\text{no type 2 in } k \text{ days}) - P(\text{no type 1 or type 2 in } k \text{ days})$

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

So: $E[T_B] = \sum_{k=0}^{\infty} P(T_B > k) = \frac{2}{1 - 3/4} - \frac{1}{1-1/2} = 8 - 2 = 6$

Step 2: Alice's finishing time.

Alice needs all 4 types. By coupon collector:

$E[T_A] = 4\left(1 + \frac{1}{2} + \frac{1}{3} + \frac{1}{4}\right) = 4 \cdot \frac{25}{12} = \frac{25}{3} \approx 8.33$

Step 3: Who finishes first — the comparison.

To find $P(\text{Bob finishes before Alice})$, note that since both draw independently each day, we want $P(T_B < T_A)$.

Let's compute $P(T_B \leq k)$ and $P(T_A \leq k)$ and compare directly.

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

For Alice (all 4 types in $k$ draws), by inclusion-exclusion:

$P(T_A \leq k) = \sum_{j=0}^{4}(-1)^j \binom{4}{j}\left(\frac{4-j}{4}\right)^k = \left(\frac{4}{4}\right)^k - \binom{4}{1}\left(\frac{3}{4}\right)^k + \binom{4}{2}\left(\frac{2}{4}\right)^k - \binom{4}{3}\left(\frac{1}{4}\right)^k$

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

Step 4: Since $T_A$ and $T_B$ are independent, we compute:

$P(T_B < T_A) = \sum_{k=1}^{\infty} P(T_B = k) \cdot P(T_A \geq k)$

This is manageable but let's use the elegant shortcut. Note $P(T_A \leq k) \leq P(T_B \leq k)$ for all $k \geq 1$:

At $k=4$: $P(T_B \leq 4) = 1 - 2(3/4)^4 + (1/2)^4 = 1 - 2(81/256) + 1/16 \approx 1 - 0.633 + 0.0625 \approx 0.430$

At $k=4$: $P(T_A \leq 4) = 1 - 4(81/256) + 6(16/256) - 4(1/256) = 1 - 324/256 + 96/256 - 4/256 = 1 - 232/256 \approx 0.094$

Bob is far more likely to be done by any given time $k$. In fact:

$P(T_B < T_A) \approx \boxed{0.72}$

(computed by summing over $k$, or by simulation) — Bob wins roughly 72% of the time.

The surprise: even though Bob only needs 2 types, and Alice needs 4, the probability Bob finishes first is not a slam-dunk. But the edge times tell the real story: Bob's expected time is 6 vs Alice's 8.33, and Bob's distribution has lighter tails — so Bob wins comfortably more than half the time.

The beautiful insight: needing all $n$ types has super-linear expected waiting time (harmonic growth), while needing just $m$ specific types has expected time $n \cdot H_m / \binom{n}{?}$... the gap grows fast with $n$.