Choose numbers from 1 to 2 n uniformly at random. How many numbers must be...

doturitip9

doturitip9

Answered

2022-07-15

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?

Answer & Explanation

Kaylie Mcdonald

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 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 )

Do you have a similar question?

Recalculate according to your conditions!

Ask your question.
Get your answer.

Let our experts help you. Answer in as fast as 15 minutes.

Didn't find what you were looking for?