Monty Hall and the Coupon Collector

Two classic puzzles show how far everyday intuition can drift from what the probabilities actually say, and how a little careful bookkeeping sets it straight. Each is worked here as a warm-up in one of the tools that stochastic modeling leans on constantly: reasoning about how new information changes the odds, and computing an average by splitting a random quantity into simple pieces.

The Monty Hall Problem

Picture a game show with three closed doors. Behind one is a car; behind each of the other two is a goat. You pick a door — say door 1 — but it stays shut for now. The host, who knows where the car is, opens one of the other two doors to reveal a goat, then asks whether you would like to switch your choice to the remaining closed door. Should you?

The Monty Hall problem (known in German as the Ziegenproblem, the “goat problem,” after Gero von Randow’s popular account) is famous for how stubbornly it fools people: when it circulated in the popular press it set off a long dispute in the letters columns, and even seasoned academics defended the wrong answer. The answer is that you should always switch — doing so doubles your chance of winning from $\tfrac13$ to $\tfrac23$.

Here is the quickest way to see it. Your original guess is right with probability $\tfrac13$ and wrong with probability $\tfrac23$, and the host’s move cannot change that first number, because he reveals a goat no matter what. So trace the two cases through to the door you would switch to:

• If your first pick was already the car (probability $\tfrac13$), the remaining closed door hides a goat, and switching loses.
• If your first pick was a goat (probability $\tfrac23$), the host is forced to reveal the other goat, so the one door he leaves closed must hide the car, and switching wins.

Switching therefore wins in exactly the case where your first guess was wrong, which happens with probability $\tfrac23$.

Laying out every branch confirms it. With your pick fixed at door 1, the car sits behind each door with probability $\tfrac13$; when it is behind your own door the host has a free choice between two goats (splitting that branch in half), and otherwise his hand is forced. The leaf probabilities are:

Each leaf probability is the product of two independent steps: the chance the car is behind that door, always $\tfrac13$, times the chance the host then opens the door shown, given where the car is. When the car is behind your own door the host may open either goat, so that second factor is $\tfrac12$ and the branch splits into two leaves of $\tfrac13 \cdot \tfrac12 = \tfrac16$ each; when the car is behind one of the other doors the host has only one goat he is allowed to reveal, so the factor is $1$ and the whole $\tfrac13$ carries through to a single leaf. The two “stick” leaves sum to $\tfrac16 + \tfrac16 = \tfrac13$; the two “switch” leaves sum to $\tfrac13 + \tfrac13 = \tfrac23$.

The whole effect hinges on one easily-missed detail: the host’s choice is not random. Because he always knows the doors and always opens a goat, the door he leaves closed carries information. When your original pick is wrong, he is effectively pointing you at the car.

The Coupon Collector’s Problem

A complete set has $n$ different collectible items — think of the player stickers sold before a football tournament — and every pack you buy holds a single sticker, equally likely to be any one of the $n$ types and independent of every other pack. On average, how many packs must you buy to complete the whole set? For a concrete case, take $n = 63$. The two assumptions doing the work are that each type is equally likely and that packs are independent.

A natural way in is to ask how the collection fills up. Suppose you already own $i$ distinct stickers. A fresh pack shows you something new only if it is one of the $n - i$ types you are still missing, so the chance of a new sticker is

When each attempt succeeds with probability $p$, the average number of attempts you wait for that success is $1/p$. So collecting the next new sticker, starting from $i$ already in hand, takes on average $\dfrac{n}{n - i}$ packs. Adding this up as the collection grows from empty to full gives the total average number of packs:

Here $E(X)$ is the expected value (the long-run average) of the random count $X$ of packs bought until the set is complete.

The same count is usually organized into phases. Phase $i$ runs from the moment you own $i - 1$ distinct stickers until you own $i$, and $X_i$ is the number of packs bought during it; the very first pack is always new, so $X_1 = 1$, and the total is

Each $X_i$ is geometrically distributed: during phase $i$ you already hold $i - 1$ types, so a pack is a “success” with probability

These are the same terms as before, only indexed by phase number instead of by how many stickers are already in hand. Because the expected value is linear (the expectation of a sum is the sum of the expectations, whether or not the pieces are independent), the phase averages simply add:

where $H_n$ is the $n$-th harmonic number.

So completing a set of $n$ items costs

packs on average — only a logarithmic factor above the $n$ stickers you are trying to collect, which as growth rates go is barely worse than linear. For the $n = 63$ stickers this works out to

roughly five times the size of the set.

Simulation and Real Data

The estimate is easy to check against real collecting. Track how many distinct stickers you hold as the total number of packs bought climbs, and the count traces a curve that rises steeply at first and then flattens as the missing types grow rare, leveling off toward the full 63. Drawing the theoretical expectation together with a one-standard-deviation band $E \pm \sigma$ around it, actual collecting runs stay inside the band the whole way and their average hugs the expectation curve. The $\mathcal{O}(n \log n)$ estimate is not just asymptotic bookkeeping — it describes what really happens when people set out to fill the album.