1
$\begingroup$

I am very new in probability and combinatorics and have a naive question around a variation on the coupon collector problem with partial collection.

Lets assume we have a box with 45 coupons labeled 1-45. Now in this case I would like to adjust the CCP such that I can calculate the expected value (amount of draws necessary) to collect 10 specific items. For example item 1-10. How do I adjust my model such that I can calculate the amount of draws necessary to collect each item n times.

I assume that I have to adjust CCP2 in following post (Coupon Collector's Problem with Partial Collections and Coupon Packages) to include the probability that I catch one item is 10/45.

All tips and tricks are welcome!

Thanks for your help

$\endgroup$
2
$\begingroup$

Let $X_n$ be the number of draws it takes to draw the $n^{th}$ desired item from the box after having drawn $X_{n-1}$ ($X_1$ is just the number of draws to draw the first item). For example $X_5$ is the number of draws it takes to draw the fifth item after the fourth item.

Then the number of draws, $X$, necessary to draw all the desired items satisfies, $$X=\sum_{n=1}^{10} X_n.$$ And consequently, $$E[X]=\sum_{n=1}^{10} E[X_n].$$

The probabiltiy of drawing the first desired item on each draw is $p_1=\frac{10}{45}$ (I'm assuming the drawn coupon is replenished which is the coupon collector problem that I'm familiar with). So $X_1 \sim \text{Geometric} (\frac{10}{45})$. Can you find the form of the rest of the $X_n$ to compute the above sum? If you want to collect each of the 10 desired items $k$ times, do you see how you can extend the work provided here?

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Yes, that helps. if I solve with recursion I get E[X] ~131,8. $\endgroup$ – Mack123456 Sep 11 '18 at 19:11
  • $\begingroup$ If I want to calculate how often I have to draw to collect each coupon 5 times I found following factor here: math.stackexchange.com/questions/151267/…. I was wondering on how to calculate or model O(n) in this answer as well as what would n be, 10/45 or just 45? $\endgroup$ – Mack123456 Sep 11 '18 at 19:17
  • $\begingroup$ Since I'm closing another question as a duplicate of this one, I'll flesh out the hint: The expected number of trials with success probability $\frac{10}{45}$ until the first success is the reciprocal $\frac{45}{10}$. After you've drawn the first desired item, there are $9$ unseen desired items left, so the probability of drawing a new desired item is now $\frac9{45}$; and so on. $\endgroup$ – joriki May 19 at 20:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.