Ferkans — Interactive Telecom Tutor

Balls, Bins, and Protocol Design

Three classic problems — balls into bins, the coupon collector, and the birthday problem — look like recreational puzzles but are in fact foundational models in algorithms, cryptography, and communications protocol design. The balls-into-bins model describes packet collisions in random access channels, hash table probing, and random placement of data in distributed storage. The coupon collector quantifies the expected time until all resources have been sampled at least once, which governs channel sounding protocols and random access convergence. The birthday problem underpins hash collision security and the capacity of slotted ALOHA channels.

All three problems reduce to the same underlying calculation: how many i.i.d.\ uniform draws from $\{1, \ldots, n\}$ are needed before a prescribed coverage condition is met?

Definition:
Occupancy Problem (Balls into Bins)

In the occupancy problem, $m$ balls are thrown independently and uniformly at random into $n$ bins. The key quantities are:

$P(\text{no empty bin}) =$ probability all $n$ bins are occupied (at least one ball each)
$P(\text{no collision}) =$ probability all $m$ balls land in distinct bins (at most one ball per bin)
$\mathbb{E}[\text{empty bins}]$ and $\mathbb{E}[\text{collisions}]$

For equal priors, the probability that all $m$ balls land in distinct bins (the no-collision event) is $P(\text{no collision}) = \frac{n!}{(n-m)!\,n^m} = \prod_{k=0}^{m-1}\!\Bigl(1 - \frac{k}{n}\Bigr).$

The occupancy problem is the continuous-time limit of the coupon collector: if we allow multiple balls per bin, the time to cover all bins is the coupon collector time.

Occupancy Problem

The random experiment of throwing $m$ balls independently and uniformly into $n$ bins, and studying the resulting occupancy distribution. Key special cases: the birthday problem ( $m$ people, $n$ birthdays) and coupon collection ( $m$ draws until all $n$ coupons seen).

Definition:
Birthday Problem

The birthday problem asks: if $m$ people each have a birthday chosen uniformly at random from $n = 365$ days, what is the probability that at least two people share a birthday?

$P(\text{collision}) = 1 - \prod_{k=0}^{m-1}\!\Bigl(1 - \frac{k}{n}\Bigr) \;\approx\; 1 - e^{-m(m-1)/(2n)}.$

The threshold is $m^* \approx \sqrt{2n\ln 2} \approx 1.177\sqrt{n}$ : once $m > m^*$ the collision probability exceeds $1/2$ .

For $n = 365$ , $m^* \approx 23$ . The surprising lesson — 23 people suffice for a 50% chance of shared birthday — shows that collision probabilities grow much faster than intuition suggests. This has profound implications for hash function security and random access.

Birthday Problem

The probability that among $m$ uniformly random draws from $\{1,\ldots,n\}$ , at least two are equal. Collision probability $\approx 1 - e^{-m^2/(2n)}$ for $m \ll n$ . The collision threshold is $m^* \approx 1.177\sqrt{n}$ .

Theorem: Birthday Bound

Let $m$ items be drawn i.i.d.\ uniformly from a set of size $n$ . The probability that all items are distinct satisfies: $e^{-m^2/(2n)} \;\leq\; P(\text{no collision}) = \prod_{k=1}^{m-1}\!\Bigl(1 - \frac{k}{n}\Bigr) \;\leq\; e^{-m(m-1)/(2n)}.$ In particular, for $m = \lfloor\sqrt{2n\ln(1/\delta)}\rfloor$ the collision probability exceeds $1 - \delta$ .

The lower bound follows from the inequality $1-x \geq e^{-x-x^2}$ for $x \in [0,1/2]$ ; the upper bound from $1-x \leq e^{-x}$ . The product then telescopes into an exponential of a sum.

Show Hint

Use $1-x \leq e^{-x}$ for each factor $1 - k/n$ in the product.

The sum $\sum_{k=1}^{m-1} k/n = m(m-1)/(2n)$ ; exponentiate.

Proof

Upper bound on $P( ext{no collision})$

Apply $1-x \leq e^{-x}$ to each factor: $P(\text{no collision}) = \prod_{k=1}^{m-1}\!\Bigl(1 - \frac{k}{n}\Bigr) \;\leq\; \prod_{k=1}^{m-1} e^{-k/n} = \exp\!\Bigl(-\sum_{k=1}^{m-1}\frac{k}{n}\Bigr) = e^{-m(m-1)/(2n)}.$

Lower bound on $P( ext{no collision})$

For $k \leq m-1 \leq n/2$ , the inequality $1-x \geq e^{-2x}$ holds for $x = k/n \leq 1/2$ . Therefore $P(\text{no collision}) \geq \prod_{k=1}^{m-1} e^{-2k/n} = e^{-m(m-1)/n} \;\geq\; e^{-m^2/n}.$ A sharper bound uses $\ln(1-x) \geq -x - x^2$ to get $e^{-m^2/(2n)}$ . $\blacksquare$

Key Takeaway

The birthday bound states that among $m \approx \sqrt{n}$ items drawn from a universe of size $n$ , a collision is roughly 50% likely. This is the fundamental limit of hash-based collision resistance: any hash function with $n$ possible outputs will have a collision after $\approx \sqrt{n}$ inputs.

Birthday Problem: Collision Probability

The probability of at least one collision among $m$ draws from a universe of size $n$ . Adjust $n$ (hash output size or number of slots) and watch the collision probability grow. The dashed line marks the threshold $m^*$ where collision probability first exceeds 0.5.

Parameters

Universe size

n

365

Maximum number of draws

m

60

Definition:
Coupon Collector Problem

Suppose there are $n$ distinct coupons. At each step, one coupon is drawn uniformly at random with replacement. Let $T_n$ be the number of draws until all $n$ coupons have been collected at least once. The coupon collector's expected waiting time is $\mathbb{E}[T_n] = n H_n = n \sum_{k=1}^n \frac{1}{k} \;\sim\; n \ln n \quad (n \to \infty),$ where $H_n$ is the $n$ -th harmonic number.

The $k$ -th new coupon is collected after a geometric waiting time with success probability $(n-k+1)/n$ . The total time is the sum of $n$ independent geometric random variables. This decomposition is the key to the proof.

Coupon Collector

A random process where items are drawn uniformly with replacement from a set of size $n$ until all $n$ items have appeared at least once. Expected waiting time: $\mathbb{E}[T_n] = n H_n \sim n \ln n$ .

Theorem: Coupon Collector's Expected Time

In the coupon collector problem with $n$ coupon types, the stopping time $T_n$ (number of draws until all $n$ types seen) satisfies $\mathbb{E}[T_n] = n H_n = n \sum_{k=1}^n \frac{1}{k},$ and the variance is $\text{Var}[T_n] = n^2 \sum_{k=1}^n \frac{1}{k^2} \;\leq\; n^2 \cdot \frac{\pi^2}{6}.$ For large $n$ , $\mathbb{E}[T_n] \approx n\ln n + 0.5772\,n$ (the Euler–Mascheroni correction), and $T_n$ is concentrated within $O(n)$ of its mean with high probability.

After collecting $k-1$ distinct coupons, the probability of drawing a new coupon on the next step is $(n-k+1)/n$ . The waiting time for the $k$ -th new coupon is geometric with this success probability, so its expectation is $n/(n-k+1)$ . Summing over all $n$ new coupons gives $n(1/n + 1/(n-1) + \cdots + 1/1) = nH_n$ .

Show Hint

Let $T_k$ be the number of draws to collect the $k$ -th new coupon after having $k-1$ distinct ones. What is $\mathbb{E}[T_k]$ ?

Write $T_n = T_1 + T_2 + \cdots + T_n$ where $T_k$ are independent geometric RVs. Apply linearity of expectation.

Proof

Decompose into geometric waiting times

Let $T_k$ be the number of draws to get the $k$ -th new coupon, given that $k-1$ distinct coupons have already been collected. At this point, there are $n-k+1$ unseen coupon types. Each draw independently produces a new coupon with probability $p_k = (n-k+1)/n$ . Therefore $T_k \sim \text{Geometric}(p_k)$ , and $\mathbb{E}[T_k] = 1/p_k = n/(n-k+1)$ .

Independence and linearity

The waiting times $T_1, T_2, \ldots, T_n$ are independent because the future draws after collecting the $(k-1)$ -th new coupon do not depend on the past (each draw is i.i.d.). Therefore $T_n = T_1 + T_2 + \cdots + T_n,$ and by linearity of expectation: $\mathbb{E}[T_n] = \sum_{k=1}^n \mathbb{E}[T_k] = \sum_{k=1}^n \frac{n}{n-k+1} = n \sum_{j=1}^n \frac{1}{j} = n H_n.$

Variance computation

For a geometric RV with success probability $p$ , the variance is $(1-p)/p^2$ . Therefore $\text{Var}[T_n] = \sum_{k=1}^n \text{Var}[T_k] = \sum_{k=1}^n \frac{1 - p_k}{p_k^2} = \sum_{k=1}^n \frac{n^2}{(n-k+1)^2} - n = n^2 \sum_{j=1}^n \frac{1}{j^2} - n \;\leq\; \frac{\pi^2 n^2}{6}. \quad \blacksquare$

Example: Coupon Collector: Numerical Illustration

A WiFi access point probes $n = 10$ orthogonal frequency-division multiple access (OFDMA) subcarriers in random order (sampling with replacement) to estimate channel state on all subcarriers. (a) What is the expected number of probes to sample every subcarrier? (b) How many probes $m$ are needed to ensure that all 10 subcarriers have been probed with probability at least $1 - 10^{-3}$ ?

Solution

Expected probes

$\mathbb{E}[T_{10}] = 10 H_{10} = 10\Bigl(1 + \frac{1}{2} + \cdots + \frac{1}{10}\Bigr) = 10 \times 2.9290 \approx 29.3 \text{ probes.}$ $

Tail bound via union bound

The probability that coupon $j$ has NOT been collected after $m$ probes is $(1 - 1/n)^m \leq e^{-m/n}$ . By the union bound over $n = 10$ coupons: $P(T_n > m) \leq n \cdot e^{-m/n}.$ Setting $n e^{-m/n} = 10^{-3}$ and solving: $e^{-m/10} = 10^{-4}$ , so $m = 40 \ln 10 \approx 92$ probes.

Interpretation

To guarantee $10^{-3}$ probability of any missed subcarrier, approximately 92 probes are needed — roughly $3\times$ the expected 29 probes. The extra probes protect against the rare event that some subcarrier goes unsampled for a long time.

Coupon Collector: Monte Carlo Simulation

Monte Carlo estimate of the coupon collector distribution. The histogram shows the empirical distribution of $T_n$ over many trials. The dashed line marks the theoretical expectation $nH_n$ . Adjust $n$ (number of coupons) to see how the distribution widens as $n$ grows.

Parameters

Number of coupons

n

20

Number of Monte Carlo trials2000

Historical Note: History of the Coupon Collector Problem

1950s–present

The coupon collector problem appeared in early probabilistic combinatorics and was a favorite of William Feller, who treated it extensively in his landmark 1950 textbook An Introduction to Probability Theory and Its Applications. The asymptotic $n \ln n$ law was known before Feller, but his textbook treatment cemented it as a standard result. The connection to harmonic numbers makes it one of the most elegant intersections of analysis, combinatorics, and probability. Modern applications range from the Lempel-Ziv universal source coding algorithm (where the time to see all $n$ -grams is $\Theta(n \log n)$ ) to cache invalidation in distributed systems.

Why This Matters: Random Access, ALOHA, and the Birthday Problem

In slotted ALOHA, $m$ devices each transmit in the same time slot with probability $1/n$ , where $n$ is the total number of slots per frame. Two devices transmitting in the same slot cause a collision. The probability of collision in a given slot given $m$ active devices is $1 - (1-1/n)^{m-1} \approx (m-1)/n$ for $m \ll n$ — exactly the birthday collision probability for 2 draws from $n$ possibilities.

The expected number of collision-free (successful) transmissions per frame is $m(1-1/n)^{m-1}$ , maximized at $m = n$ with throughput $1/e$ — the classic ALOHA capacity. Increasing $m$ beyond $n$ triggers the birthday effect and throughput collapses. The coupon collector analysis then tells us how many collision-free rounds are needed for every device to transmit successfully at least once: approximately $n \ln n$ .

Monte Carlo Coupon Collector Simulation

Complexity:

O(N_\text{trials} \cdot n \log n)

expected

Input:

n

(coupons),

N_\text{trials}

(number of trials)

Output: Empirical distribution of

T_n

1. Initialize

\text{stopping\_times} \leftarrow []

2. for trial

= 1, \ldots, N_\text{trials}

do

3.

\text{collected} \leftarrow \emptyset

(empty set of seen coupons)

4.

t \leftarrow 0

5. while

|\text{collected}| < n

do

6.

c \leftarrow \text{Uniform}\{1, \ldots, n\}

7.

\text{collected} \leftarrow \text{collected} \cup \{c\}

8.

t \leftarrow t + 1

9. end while

10. Append

t

to

\text{stopping\_times}

11. end for

12. return

\text{stopping\_times}

The inner loop runs for $\mathbb{E}[T_n] = nH_n$ iterations in expectation. For large $n$ , the simulation slows but analytical formulas suffice.

Quick Check

A channel sounder must probe $n = 100$ frequency subcarriers, sampling randomly with replacement. The expected number of probes to cover all 100 subcarriers is closest to:

100

519

1000

100 \ln 100 \approx 460$

Correction:

519

$\mathbb{E}[T_{100}] = 100 H_{100} \approx 100 \times 5.187 = 518.7 \approx 519$ .

Common Mistake: Birthday Problem Intuition Failure

Mistake:

Students often guess that the birthday collision threshold (50% probability of two people sharing a birthday) is around $n/2 \approx 182$ people, since there are 365 possible birthdays and you need to "fill half of them."

Correction:

The threshold is $m^* \approx \sqrt{2 \cdot 365 \cdot \ln 2} \approx 23$ , not $365/2$ . The quadratic growth of collision probability ( $\sim m^2/(2n)$ ) arises because we are comparing every pair, not just counting distinct values. With $m$ people there are $\binom{m}{2} \approx m^2/2$ pairs, each with probability $1/n$ of collision. The expected number of collisions is $m^2/(2n)$ , which reaches 1 when $m \approx \sqrt{2n}$ .

Three Occupancy Problems: Balls into Bins

Problem	Question	Key Formula	Wireless Analog
Birthday problem	P(no collision) among $m$ draws from $\{1,\ldots,n\}$	$\approx e^{-m^2/(2n)}$ ; threshold $m^* \approx 1.18\sqrt{n}$	Hash collision; slotted ALOHA collision probability
Coupon collector	$\mathbb{E}[T_n]$ : draws to see all $n$ coupons	$nH_n \approx n\ln n$	Channel sounding: probes to sample all subcarriers; MAC-layer coverage
Occupancy distribution	$P($ exactly $k$ bins empty $)$ after $m$ throws	Stirling numbers; $\sum_k \binom{n}{k}(-1)^k (1-k/n)^m$	Load balancing; distributed hash table utilization

Matching, Occupancy, and Coupon Collection

Balls, Bins, and Protocol Design

Definition: Occupancy Problem (Balls into Bins)

Occupancy Problem

Definition: Birthday Problem

Birthday Problem

Theorem: Birthday Bound

Upper bound on $P( ext{no collision})$

Lower bound on $P( ext{no collision})$

Key Takeaway

Birthday Problem: Collision Probability

Parameters

Definition: Coupon Collector Problem

Coupon Collector

Theorem: Coupon Collector's Expected Time

Decompose into geometric waiting times

Independence and linearity

Variance computation

Example: Coupon Collector: Numerical Illustration

Expected probes

Tail bound via union bound

Interpretation

Coupon Collector: Monte Carlo Simulation

Parameters

Historical Note: History of the Coupon Collector Problem

Why This Matters: Random Access, ALOHA, and the Birthday Problem

Monte Carlo Coupon Collector Simulation

Quick Check

Common Mistake: Birthday Problem Intuition Failure

Three Occupancy Problems: Balls into Bins

Definition:
Occupancy Problem (Balls into Bins)

Definition:
Birthday Problem

Definition:
Coupon Collector Problem