Mix $T\geq1$ coupons numbered $1$ to $T$ with a set of $S\geq0$ number of dummy coupons with no numbers. Select $N\geq1$ coupons at each trial at random and put them back.

$N=1$ is standard coupon collector problem. I have not seen any reference for $N>1$.

1. What is the probability that after $k$ trials you selected each coupon from $1$ to $T$ at least once?

2. What is the expected number of trials one needs to select each coupon from $1$ to $T$ at least once with probability $1-\frac{1}{c}$ for some $c>1$?

3. Fix a coupon $x_t\in\{1,\dots,T\}$. How many trials to do you expect to have to select this particular coupon at least once with probability $1-\frac{1}{c}$ for some $c>1$?

I am looking for sharp asymptotics.

  • $\begingroup$ Not an asymptotic but exact answer for question 1: $$\binom{T+S}{N}^{-k} \sum_{i=0}^T (-1)^i \binom{T}{i} \binom{T-i+S}{N}^k.$$ $\endgroup$ – Max Alekseyev Aug 18 '15 at 18:42
  • $\begingroup$ If $N=1$ then the expectation is $(S+T)H_T$ $\endgroup$ – Henry Aug 18 '15 at 20:16
  • $\begingroup$ @Henry Yes. $N=1$ is standard. What about $N>1$? $\endgroup$ – user76479 Aug 19 '15 at 1:21
  • $\begingroup$ @MaxAlekseyev I am not getting prob <1? Could you write your proof? $\endgroup$ – user76479 Aug 19 '15 at 1:44
  • $\begingroup$ @Arul: What are your numerical values? The formula follows from the inclusion-exclusion principle. $\endgroup$ – Max Alekseyev Aug 19 '15 at 2:06

Your Answer

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