3
$\begingroup$

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.

Improve this question
$\endgroup$
9
  • $\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
    Commented Aug 18, 2015 at 18:42
  • $\begingroup$ If $N=1$ then the expectation is $(S+T)H_T$ $\endgroup$
    – Henry
    Commented Aug 18, 2015 at 20:16
  • $\begingroup$ @Henry Yes. $N=1$ is standard. What about $N>1$? $\endgroup$
    – user76479
    Commented Aug 19, 2015 at 1:21
  • $\begingroup$ @MaxAlekseyev I am not getting prob <1? Could you write your proof? $\endgroup$
    – user76479
    Commented Aug 19, 2015 at 1:44
  • $\begingroup$ @Arul: What are your numerical values? The formula follows from the inclusion-exclusion principle. $\endgroup$
    – Max Alekseyev
    Commented Aug 19, 2015 at 2:06

0

Reset to default

You must log in to answer this question.