I am trying to solve this question on Sedgewick's and Wayne's Algorithms book:
Suppose that a linear-probing table of size 10^6 is half full, with occupied positions chosen at random. Estimate the probability that all positions with indices divisible by 100 are occupied.
So we had 500.000 inserts on the hash table and need to check the probability of positions 0, 100, 200, ..., 99900 being occupied. So far I thought about calculating the events one by one: On the first insert there are 10^4 / 10^6 probability of inserting in an index divisible by 100. On the second, we have to consider that the first index divisible by 100 was chosen, so there is a 9.999 / 10^6 probability.
And since we have more inserts (500.000) than indices divisible by 100, I thought about computing the probability of 10.000 inserts occupying the indices divisible by 100 and then multiplying this probability by 50, since we could "try" this insert pattern 50 times.
P = (10.000 / 10^6 * 9.999 / 10^6 * ... * 1 / 10^6) * 50
Is this line of thought correct? Also, the tricky part here is that we are talking about a linear-probing hash table. So if we insert an element on index 99 twice, the second element will occupy index 100. This also means that inserting an element on index 1 100 times will mean that index 100 is occupied. I am not sure how to deal with this extra requirement. Any ideas?