# Collecting coupons

• Jul 1st 2009, 06:36 PM
acc100jt
Collecting coupons
Suppose that there are $\displaystyle N$ distinct tyoes of coupons and each time one obtains a coupon it is, independent of prior selections, equally likely to be any one of the $\displaystyle N$ types. One random variable of interest is $\displaystyle T$, the number of coupons that needs to be collected until one obtains a complete set of at least one of each type. Rather than derive $\displaystyle P\{T=n\}$ directly, let us start by considering the probability that $\displaystyle T$ is greater than $\displaystyle n$. To do so, fix $\displaystyle n$ and define the events $\displaystyle A_{1}, A_{2}, ..., A_{N}$ as follows: $\displaystyle A_{j}$ is the event that no type $\displaystyle j$ coupon is contained among the first $\displaystyle n$, $\displaystyle j=1, ..., N$.
Hence, $\displaystyle P\{T>n\}=P\left(\bigcup^{N}_{j=1}A_{j}\right)$

I coulnd't understand the last equality, and why can't we derive $\displaystyle P\{T=n\}$ directly?

Appreciate those who help!!
• Jul 3rd 2009, 04:50 AM
Laurent
Quote:

Originally Posted by acc100jt
Suppose that there are $\displaystyle N$ distinct tyoes of coupons and each time one obtains a coupon it is, independent of prior selections, equally likely to be any one of the $\displaystyle N$ types. One random variable of interest is $\displaystyle T$, the number of coupons that needs to be collected until one obtains a complete set of at least one of each type. Rather than derive $\displaystyle P\{T=n\}$ directly, let us start by considering the probability that $\displaystyle T$ is greater than $\displaystyle n$. To do so, fix $\displaystyle n$ and define the events $\displaystyle A_{1}, A_{2}, ..., A_{N}$ as follows: $\displaystyle A_{j}$ is the event that no type $\displaystyle j$ coupon is contained among the first $\displaystyle n$, $\displaystyle j=1, ..., N$.
Hence, $\displaystyle P\{T>n\}=P\left(\bigcup^{N}_{j=1}A_{j}\right)$

I coulnd't understand the last equality, and why can't we derive $\displaystyle P\{T=n\}$ directly?

Appreciate those who help!!

The equality is just a translation from words to maths of a simple statement, namely "The event $\displaystyle \{T>n\}$ means that among the first n coupons there is a missing type $\displaystyle j\in\{1,\ldots,N\}$ of coupons". This should be clear (otherwise, give it a second thought ; remember $\displaystyle T$ is the first time we have all types of coupons).
Then $\displaystyle \bigcup_{j=1}^N A_j$ is the event "There exists $\displaystyle j\in\{1,\ldots,N\}$ such that $\displaystyle A_j$ happens", and here we are since $\displaystyle A_j$ is defined as: "the type $\displaystyle j$ is missing among the $\displaystyle n$ first coupons".

About $\displaystyle P(T=n)$, if you can derive it directly, that's just fine! It is probably easier however (here and in a large variety of situations) to find $\displaystyle P(T>n)$ and then deduce the first one by $\displaystyle P(T=n)=P(T>n-1)-P(T>n)$.