How does the Coupon Collector problem change when you're only trying to collect a subset of the coupons?

323 Views Asked by At

If there are 100 tickets in an urn, and I'm only trying to see 10 of them while drawing with replacement, how do I find the result for that?

My intuition makes me want to say it's $n\sum_{i=1}^k\frac{1}{i}$ where $n$ is the total number of tickets, and $k$ is the number of tickets you're actually trying to collect.

1

There are 1 best solutions below

0
On BEST ANSWER

You can use the usual technique. Let $N_{i}$ denote the number of tickets until you see the $i$-th new ticket among the $k$. Also, let $N$ denote the number of tickets untill all $k$ tickets are seen. Since $N=\sum_{i=1}^{k}{N_i}$, conclude that \begin{align*} E[N] &= E\left[\sum_{i=1}^{10}{N_i}\right] \\ &= \sum_{i=1}^{10}E[N_i] \end{align*} Note that $N_i$ follows a geometric distribution with parameter $\frac{k+1-i}{n}$. Therefore $E[N_i]=\frac{n}{k+1-i}$ and $E[N] = n\sum_{i=1}^{k}{\frac{1}{k+1-i}} = n\sum_{i=1}^{k}{\frac{1}{i}}$.