1
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Nice, this solves part of the problem. But since this is a linear-probing hash table, choosing more than once a non-divisible-by-100 index may lead to an index divisible by 100 being occupied. That would be the equivalent of choosing more than once a white ball leading to a choice of a black ball in the simple problem. And this “more than once” is different (ranging from 2 to 99), depending on the index of the white ball. In fact, if we choose the same black ball 100 times, that would be the equivalent of choosing the next black ball. Any ideas in this case? $\endgroup$ – Rene Argento Jul 21 '17 at 22:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.