Probability that all indices divisible by 100 in a hash table with linear probing are occupied

Question

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?

Answer 1

This problem may be reduced to the following simple probability problem with concrete numbers.

Assume you have an urn with 8 black and 12 white balls, total 20 balls. You randomly draw 15 balls from the urn one by one without replacement. What is the probability that all black balls are selected?

How does it relate to the original problem? Occupying slots one by one is equivalent to drawing balls without replacement. Both number of slots and balls decrease. "Drawing a ball" corresponds to "eventually occupying a slot" after linear probing (searching).

We have address space of $10^6$ slots equivalent to having $10^6$ balls in an urn. Then you have positions with indices divisible by 100 equivalent to having $10000$ $(=10^6/100)$ black balls. $500000$ positions are occupied means that you draw $500000$ balls. Finally, the requirement "all positions with indices divisible by 100 $(=10^6/100)$ are occupied" means "all $10000$ black balls must be selected".

Thus it is the hypergeometric distribution that describes the probability of $k$ successes in $n$ draws, without replacement, from a finite population of size $N$ that contains exactly $K$ successes, wherein each draw is either a success or a failure (black or white). The probability is equal to

$$ P(k \text{ successes})= \frac{\binom{K}{k}\binom{N-K}{n-k}}{\binom{N}{n}}$$

So, if we take urn-balls model then we have $$ P(8 \text{ black balls})= \frac{\binom{8}{8}\binom{20-8}{15-8}}{\binom{20}{15}}$$

As for the original problem then we have $$ P(10000 \text{ occupied slots})= \frac{\binom{10000}{10000}\binom{10^6-10000}{500000-10000}}{\binom{10^6}{500000}}$$

Now, our numbers in the original problem is too large to compute the binomial coefficients. You could get around the problem using Stirling's approximation.