0
$\begingroup$

I came across this paper which gives bounds on weighted coupon collector problem. This paper, in short, tries to prove various lower and upper bounds for the expected number of draws till we see all coupons. U1 is one of the upper bounds for the expectations. Page 451 contains a table where reference to U1 is given as 'folklore'. I presume this is trivial to follow from the definition but I can't see the logic behind this. Does anyone have hints for me? I tried to get this bound by taking the limit of probability that some coupon is not found after n tries but that needs n to be infinity.

$\endgroup$
  • $\begingroup$ Would be nice to describe in brief what the paper says. $\endgroup$ – Shailesh Sep 23 '15 at 2:47
  • $\begingroup$ @Shailesh This is the weighted coupon collector problem. The paper tries to prove various lower and upper bounds for the expected number of draws till we see all coupons. U1 is one of the upper bounds for the expectation. $\endgroup$ – vlogtest554863 Sep 23 '15 at 3:01
  • $\begingroup$ I'm adding that to the question. $\endgroup$ – Shailesh Sep 23 '15 at 4:09
0
$\begingroup$

$\frac{\log n}{p_1}$ is not an upper bound for the expected number of coupons drawn, since it's zero for $n=1$.

However, replacing $\log n$ by $H_n$ yields $\frac{H_n}{p_1}$, which is an upper bound since it's the expected number of coupons drawn if we reduce the drawing probability of all coupons to $p_1$.

$\endgroup$

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.