> “How many times do you have to roll an n-sided die to ensure you’ve seen each side at least m times?” This is an extension of the coupon collector's problem

> “How many times do you have to roll an n-sided die to ensure you’ve seen each side at least m times?” This is an extension of the coupon collector's problem (which addresses the m=1 case). Per the Wikipedia page: > Donald J. Newman and Lawrence Shepp gave a generalization of the coupon collector's problem when m copies of each coupon need to be collected. Let T_m be the first time m copies of each coupon are collected. They showed that the expectation in this case satisfies: > E[T_m] = n log n + (m-1) * n * log log n + O(n), as n -> infinity https://en.wikipedia.org/wiki/Coupon_collector%27s_problem#Extensions_and_generalizations https://en.wikipedia.org/wiki/Coupon_collector%27s_problem#E... edit: If you're familiar with that problem, then you can use the tail estimate for 1 copy per shard with 99.99% probability for 128 shards (per the linked gist) to arrive at ~1800 -- it's a matter of computing beta such that n^{-beta + 1} = 0.01%, so beta ~ 2.9; I then calculated beta * n log n to arrive at 1801. Given the scaling of the expectation above, you can observe the difference between "get at least 1" and "get at least 2 of each" is fairly small in the grand scheme of things. And, incidentally, the second term 128 * log(log(128)) is just about 200 (for a total of about 2000), so not too far off from the simulation result in the blog post.