User tal k - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-23T06:14:03Z http://mathoverflow.net/feeds/user/3588 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/13171/how-many-trial-picks-expectedly-sufficient-to-cover-a-sample-space/13184#13184 Answer by Tal K for How many trial picks expectedly sufficient to cover a sample space? Tal K 2010-01-27T20:41:56Z 2010-01-27T20:51:26Z <p>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.</p> http://mathoverflow.net/questions/13171/how-many-trial-picks-expectedly-sufficient-to-cover-a-sample-space/13184#13184 Comment by Tal K Tal K 2010-01-27T21:47:15Z 2010-01-27T21:47:15Z Kevin, your alternative model with p=1/2 is the Erdos-Renyi &quot;20 Questions&quot; 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). http://mathoverflow.net/questions/13171/how-many-trial-picks-expectedly-sufficient-to-cover-a-sample-space/13184#13184 Comment by Tal K Tal K 2010-01-27T20:59:10Z 2010-01-27T20:59:10Z Yes, &quot;at most&quot;, meaning that the slower coverage process takes (n/r)*log(n). Thanks for catching that. Also, when I say &quot;a close approximation&quot; 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 &quot;constant&quot;, as in the Erdos-Renyi problem. It would take a more detailed calculation to find out.