Probability with replacement?

Question

A library has 2million books. You check out 16 books at random. Tomorrow (and each subsequent day), you return those 16, & check out 16 random books. When do you have a 50% chance of checking out at least 1 book you've previously gotten? When do you have a 50% chance of checking out 8 (of the 16) previous books (and what are the formulas)?

Answer 1

Here is how I approached this: To keep the problem tractable, assume that there are 10 books and you picked 1 at a time.

On the second day, you have a 1/10=10% chance that you will repeat a book

For the third day, we should proceed as follows. The number ways you could choose 3 books over 3 days is 10^3. The number of ways of choosing 3 different books is 10x9x8. Therefore the probability that they are all different = 10x9x8/1000 = 72%. Therefore the probability at least one repeats = 28%. Add that to the number above and you have 38% for day 3. You can repeat this for several days and get at what day this becomes > 50%.

For this example, its on day 4.

For the library example you quote, for any given day 'r', the incremental probability is

P(r) = 1 - (r! nCr)/n!.

and what you want to do is find an 'r' such that SUM P(r) >= 0.5.

Answer 2

This is one of those problems where you calculate the probability of something NOT happening, and as the last step subtract it from 1.

So, the probability of NOT getting a repeat with the first book on the second day is (2 million - 16)/2 million. The probability of NOT getting a repeat with the second book on the second day is (2 million - 17)/(2 million -1). And so on. The probability of of NOT getting a repeat anywhere in the 2nd day through the 1001st day is the product of 16,000 terms like that.

I'm blanking for a moment on the second harder part. Look at binomial probabilities for inspiration. If there's a whole other way to do the problem, I'm not seeing the trick yet.