Choose numbers from 1 to 2 n uniformly at random. How many numbers must be chosen, on average, before at least n numbers have been picked?

Question

Choose numbers from   1 to   2  n uniformly at random. How many numbers must be chosen, on average, before at least   n numbers have been picked?

Kaylie Mcdonald · Accepted Answer

If you stop the sum from the coupon collector problem half-way, you get your answer. It takes   1 draw on average to get the first different ticket, then             2      n              2      n      −      1       draws for the second, and so on until             2      n              n      +      1       for the       n          t      h      . So this is   2  n  ∗  (      H          2      n        −      H    n    )