We have $k$ different types of coupons (with replacement).If we collect at least $l$ different coupons, we win a prize. We can only afford to collect $m$ coupons.


Let's say we take all those $m$ coupons, and we collect exactly $L$ different coupons. Then the probability that we win a prize is $P(L \geq l)$


Let $T$ be the number of trials taken to collect exactly $l$ coupons. Then the probability we win a prize is $P(T \leq m)$


"Clearly" $P(L \geq l) = P(T \leq m)$.


So how on earth does one go about proving it rigorously? I'm not too familiar with the theory of stopping times, and the proof may come from that area, but no treatise that mentions these two problems ever seems to prove this equality. Does anyone know of someone that has taken the time to prove this rigorously, and what formalism that they use?



Rigorous proof of the duality of Coupon collector's problem and Occupancy problem
To specify the probability space is rarely a good idea but since you insist on it, a possible choice would be $\Omega=K^\mathbb N$, where $K=\{1,2,\ldots,k\}$ denotes the set of types of coupons, endowed with the sigma-algebra ${\mathcal K}=2^K$ and the discrete measure $p=(p\_i)$ on $(K,\mathcal K)$ describing the probability to get a coupon of a given type at each draw. In other words, for every $A\subseteq K$, $A\in\mathcal K$ and $p(A)=\sum\limits\_{i\in A}p\_i$.


This considers that one collects coupons again and again, even when one is really interested in what happens with the $m$ first coupons collected.


As a product space, $\Omega$ is endowed with the product sigma-algebra $\mathcal F=\mathcal K^{\otimes\mathbb N}$, generated by the cylinders $A\times K^\mathbb N$ with $A\subseteq K^n$ and $n\in\mathbb N$, and with the product probability measure $\mu=p^{\otimes\mathbb N}$. Thus, $\mu$ is the unique probability measure such that, for every positive $n$ and every $\eta=(\eta\_t)$ in $K^n$, $\mu(\Omega\_\eta)=\prod\limits\_{t=1}^np\_{\eta\_t}$, where $\Omega\_\eta=\{\omega=(\omega\_n)\_{n\in\mathbb N}\in\Omega\mid\forall t\leqslant n,\omega\_t=\eta\_t\}$.


For every $\omega=(\omega\_n)\_{n\in\mathbb N}$ in $\Omega$ and every $n\in\mathbb N$, define $N\_n(\omega)$ as the size of the set $\{\omega\_t\mid t\leqslant n\}$. Then each $N\_n$ is a random variable on $(\Omega,\mathcal F)$. Furthermore, for every positive $\ell$, the number $T\_\ell$ of draws needed to collect exactly $\ell$ different coupons is such that $[T\_\ell\leqslant m]=[N\_m\geqslant\ell]$ and, for every positive $m$, the number $L\_m$ of different coupons collected during the $m$ first draws is $L\_m=N\_m$. This proves that $[T\_\ell\leqslant m]=[L\_m\geqslant\ell]$ for every positive $m$ and $\ell$.


