doturitip9

2022-07-15

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

Kaylie Mcdonald

Expert

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 $\frac{2n}{2n-1}$ draws for the second, and so on until $\frac{2n}{n+1}$ for the ${n}^{th}$. So this is $2n\ast \left({H}_{2n}-{H}_{n}\right)$

Do you have a similar question?