0
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • 5
    $\begingroup$ Unless I'm missing something, it follows immediately from the setup/definitions that $T\leq m$ if and only if $L\ge l$. Indeed, the text of your question seems to take it for granted that each of these just gives a different description for the event "we win." $\endgroup$
    – Ed Dean
    Commented Apr 3, 2012 at 16:42
  • $\begingroup$ Okay then, what is the sample space that these events are defined over? T and L can be described as random variables over the set of all sequences of picks which is uncountable and un-measureable. Though i suppose i could truncate it to all sequences of length m and allow T to be "Never". But then we can't define its variance or expectation, and its those that i am interested in. $\endgroup$
    – user20886
    Commented Apr 3, 2012 at 19:38
  • 3
    $\begingroup$ Why do you say the space of all sequences of picks is unmeasurable? It seems to carry a perfectly good product measure, with respect to which the event you're interested in (described by the equivalent inequalities $L\geq l$ and $T\leq m$ or by the plain statement that there are at least $l$ different coupons among the first $m$ terms of the sequence) is a measurable set. So I don't see any real problem here. $\endgroup$
    – Andreas Blass
    Commented Apr 4, 2012 at 23:18

1 Answer 1

Reset to default
6
$\begingroup$

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$.

Improve this answer
$\endgroup$
2
  • $\begingroup$ I might add that you can instead define the probability space to be the reals $[\0 \ldots 1)$. Then for a particular real you take it's digital representation in base $k$ as your sequence. This is essentially the same as your answer, except you get the structure of the sigma-algebra and probability space "for free". $\endgroup$
    – user20886
    Commented Apr 15, 2012 at 9:51
  • $\begingroup$ For some reason i can't edit, but the range in question is $[0,1)$ and the digital representation is all those digits occurring after the decimal point. $\endgroup$
    – user20886
    Commented Apr 15, 2012 at 9:52

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .