User tal k - MathOverflow

Answer by Tal K for How many trial picks expectedly sufficient to cover a sample space?

2010-01-27T20:41:56Z

This process will cover the set faster than making $r$ random selections of a single element at each step ("sampling with replacement", producing a multiset of $r$ not-necessarily-distinct elements instead of a set of $r$ distinct elements). The latter is taking $r$ steps at a time in the Coupon Collector process which takes $n * log(n)$ steps. So we need at least $(n/r) * log(n)$ steps on average. This should be a close approximation when $n/r$ is large and within a bounded (not necessarily constant) factor of the truth when $n/r$ is bounded. The case when $n=2r$ is close to the "20 questions" problem of Erdos and Renyi.

Comment by Tal K

2010-01-27T21:47:15Z

Kevin, your alternative model with p=1/2 is the Erdos-Renyi "20 Questions" problem, and the expected coverage time in that case involves both the [base 2] log(n) and some function of the fractional part of log(n). That's not necessarily inconsistent with your remark (for instance the log-periodic term could be additive, not multiplicative, I don't have the reference handy to check which it is).

Comment by Tal K

2010-01-27T20:59:10Z

Yes, "at most", meaning that the slower coverage process takes (n/r)*log(n). Thanks for catching that. Also, when I say "a close approximation" I suppose that the asymptotic difference between the with- and without- replacement expected times (in the case when n/r is large) would be an additive difference of O(log n), not a multiplicative difference of a constant factor in the larger main term. In the n/r bounded case there could well be some log-periodic function as the "constant", as in the Erdos-Renyi problem. It would take a more detailed calculation to find out.