doturitip9

Answered

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?

Answer & Explanation

Kaylie Mcdonald

Expert

2022-07-16Added 19 answers

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 ({H}_{2n}-{H}_{n})$

Most Popular Questions