Birthday & Coupon Collector

Medium2–3 hrsBirthdayCoupon CollectorExpected Value

Overview

These two problems share a deep structure: both involve waiting for something to happen in a large sample space. Birthday teaches you that coincidences happen far sooner than intuition expects. Coupon Collector teaches the harmonic series — the last few items are expensive to collect because you keep getting repeats. Both are about the tension between what feels rare and what is probabilistically inevitable.

How to Recognize

→How many trials until a collision (two people share a birthday)?
→How many trials to see all n distinct outcomes at least once?
→Pigeonhole principle: n items in n−1 boxes → at least one box has 2

Step-by-Step Approach

1.Birthday: P(no collision with k people) = (365/365)·(364/365)·…·(365−k+1/365)
2.Approximate: P(collision) ≈ 1 − e^(−k(k−1)/(2n)). Set = 0.5 → k ≈ 1.177√n
3.Coupon Collector: at stage i (have i−1 types), P(new type) = (n−i+1)/n
4.E[total] = Σ n/(n−i+1) for i=1..n = n·H(n) ≈ n·ln(n)

Key Formulas

P(\text{collision by }k) \approx 1 - e^{-k^2/2n}

0250% collision:

k \approx 1.177\sqrt{n}

(for

n=365

k \approx 23

)

E[\text{coupon collector}] = n H_n = n\sum_{k=1}^n \frac{1}{k} \approx n(\ln n + 0.577)

n=365

: need ~23 people for 50% birthday collision

Worked Examples

0Quick Example

Coupon collector with 6 types: E[draws] = 6·(1 + 1/2 + 1/3 + 1/4 + 1/5 + 1/6) = 6·49/20 = 14.7.

Problem

How many people do you need in a room so that P(at least two share a birthday) ≥ 50%? Assume 365 equally likely birthdays.

Solution

Compute P(no collision with k people): person 1 has any birthday. Person 2 avoids it: 364/365. Person 3 avoids both: 363/365. Etc.

P(no collision) = 365/365 · 364/365 · … · (365−k+1)/365

Approximation: P(no collision) ≈ e^(−k(k−1)/(2·365)). Set = 0.5.

Solve: k(k−1)/730 = ln(2) ≈ 0.693 → k² ≈ 506 → k ≈ 22.5, so k = 23.

Exact calculation confirms P(collision with 23 people) ≈ 50.7%.

Answer

23 people gives P(collision) ≈ 50.7%. The formula $k \approx 1.177\sqrt{n}$ gives $1.177\sqrt{365} \approx 22.5$ . Most people guess 183 — the answer is shockingly small.

Common Mistakes

!
Thinking the birthday problem needs birthdays to match YOUR birthday specifically. It asks for ANY match among all pairs — there are C(k,2) pairs, which is why it's so likely.
!
Coupon Collector: forgetting that the last stage takes n boxes on average. The variance is also large — you might get lucky or very unlucky at the end.
!
Not using the complement/approximation. The exact birthday calculation is a product of fractions that is tedious. The approximation e^(−k²/2n) is accurate enough for interviews.

Practice Problems

Click "Show Answer" to reveal

How many random integers from 1–100 do you need to pick (with replacement) to have a 50% chance that two are the same?

Hint: Birthday problem with n=100.

A card is drawn uniformly from a deck of 52. If you draw cards with replacement, how many draws on average until you've seen all 52 cards?

Hint: Coupon Collector with n=52.

13 socks in a drawer: 6 black and 7 white. Minimum draws to guarantee a matching pair?

Hint: Pigeonhole: worst case before a match.

Back to Study Plan

Conditional Probability & Bayes Inclusion-Exclusion