4
$\begingroup$

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?

This is similar to the coupon-collector problem, but looking for only partial completion.

Note: Choosing an appropriate meaning of 'random' is part of the question.

1 Answers 1

5

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*(H_{2n}-H_n)$

Of course, if you choose without replacement, the answer is n draws.

  • 0
    Great! Easter than I had thought. So for n items and any fraction a, it should take about n log (1/a), or more precisely n log((n + 0.5)/(an + 0.5)).2010-10-21