0
$\begingroup$

I have a problem where I'm trying to calculate the probability of getting a full bucket when I use a hash table with open addressing.

What I have:

  • A hash table with 128 buckets, each bucket can store 2 entries.
  • Maximum 64 key-value pairs will be inserted into the table.
  • I have a hash function which takes a key and returns a 32-bit hash value. For simplicity we can assume that this functions give me a uniform distributions among all the buckets. I.e. if I would insert $2^{32}$ keys into the hash table, each bucket would contain exactly the same amount of key-value pairs.

What is the probability that I will fill at least one of the buckets (i.e. get 3 or more key-value pairs in the same bucket)?

What I have tried so far:

  • I have tried making a simple analogy where I would pick balls of different colors from a bag. The number of balls in total would be 2^32 (all the possible hash values), the number of colors would be 128 and I would the pick 64 balls without putting them back. You can find that question ask here.

Using the formula from that question I would get the probability like this:

$$ {\sum_{r=3}^{64} \binom{2^{32} \over 128}{r} * \binom{2^{32} - {2^{32} \over 128}}{64 - r} \over \binom{2^{32}}{64}} * 128 \approx 1.78 $$

A probability of 178% doesn't seem right so I must be doing something wrong. @AndreNicolas told me that I'm double counting using this method and I should use Inclusion/Exclusion but even after reading about it I'm not sure how to use it.

$\endgroup$
1
$\begingroup$

So, you have $2^{32}$ cards total, with $2^7$ different suits, each with $2^{25}$ cards in them, and you are asking for the probability of when pulling a hand of $64$ cards getting at least one suit with 3 or more cards in it.

As you say, let us look at ways in which we pick a specific suit to be overloaded with cards: There are $2^7$ different suits to choose from to be intended to be overloaded, from within the intentionally overloaded suit it could have had 3, 4,...,r,... on up to 64 cards in it for a total of $\binom{2^{25}}{r}$ ways of picking $r$ cards for the intentionally overloaded suit. Finally, for the other suits, we ignore whether or not they become overloaded (we will account for that mistake later by applying inclusion-exclusion), and we need to pick the remaining $(64-r)$ cards for our hand from the $2^{32}-2^{25}$ remaining cards.

That brings us to the formula you proposed:

$$\frac{\sum\limits_{r=3}^{64}\binom{2^{25}}{r}\binom{2^{32}-2^{25}}{64-r}\binom{2^{7}}{1}}{\binom{2^{32}}{64}}$$

As mentioned by Andre however, this overcounts situations where two (or more) suits are intended to be overloaded, so we need to subtract that.

To have two suits intentionally overloaded, first we choose which two suits they are: $\binom{2^7}{2}$, then from the first intentionally overloaded suit pick $r$ cards with $3\leq r\leq 61$, and from the second intentionally overloaded suit pick $s$ cards with $3\leq s\leq 64-r$, and from the remaining suits, ignoring whether or not they become overloaded we pick the remaining $64-r-s$ cards.

So, we arrive at:

$$\frac{\sum\limits_{r=3}^{64}\binom{2^{25}}{r}\binom{2^{32}-2^{25}}{64-r}\binom{2^{7}}{1} - \sum\limits_{r=3}^{61}\sum\limits_{s=3}^{64-r}\binom{2^{25}}{r}\binom{2^{25}}{s}\binom{2^{32}-2^{26}}{64-r-s}\binom{2^7}{2}}{\binom{2^{32}}{64}}$$

...But wait... in subtracting that many, we accidentally subtracted too much. We then add back the probability of three suits being chosen to intentionally be overloaded, and then subtract again the probability of four suits being chosen to intentionally be overloaded, and then add the probability of five suits being intentionally overloaded, etc... on up until it is finally impossible for all of our designated suits to be intentionally overloaded (The final term being with 21 suits each having 3 cards a piece or one of them with four cards, but it is impossible to have 22 suits overloaded as that would require at least 66 different cards in the hand).

The exact probability then will be:

$$\frac{\sum\limits_{r=3}^{64}\binom{2^{25}}{r}\binom{2^{32}-2^{25}}{64-r}\binom{2^{7}}{1} - \sum\limits_{r=3}^{61}\sum\limits_{s=3}^{64-r}\binom{2^{25}}{r}\binom{2^{25}}{s}\binom{2^{32}-2^{26}}{64-r-s}\binom{2^7}{2}+A_3-A_4+A_5-\cdots + A_{21}}{\binom{2^{32}}{64}}$$

Where $A_{k} = \sum \binom{2^{25}}{a_1}\binom{2^{25}}{a_2}\cdots\binom{2^{25}}{a_k}\binom{2^{32}-k2^{25}}{64-a_1-a_2-\dots -a_k}\binom{2^7}{k}$ where the sum ranges over all possible integer values of $a_1,a_2,\dots a_k$ satisfying $a_i\geq 0$ and $\sum\limits_{i=1}^k a_i \leq 64$ for all $i\in\{1,2,\dots,k\}$

This is, unfortunately, a very tedious problem that if you want an answer would help to have a computer calculate for you (it won't be as simple an answer to come up with via pen&paper as your previous version of the question). As Andre points out though, as $k$ gets larger, the terms get successively smaller in size, so you can come up with a rather good approximation by using just the first four or five terms.


We could also have approached this from the opposite direction: Find the probability of no suit having three or more cards. If this happens, there will be:

  • Some suits with 2 cards each
  • Some suits with 1 card each
  • The rest of the suits with 0 cards each

Suppose we have $r$ suits with $2$ cards each, then there are $64-2r$ suits with $1$ card each, and $2^7 - r - (64-2r) = 2^7-64+r$ suits with zero cards each.

With $r$ given, we pick how many ways there are to choose the suits, and then choose the cards within each suit:

$$\binom{2^7}{r}\binom{2^7-r}{64-2r}\binom{2^{25}}{2}^r(2^{25})^{64-2r}$$

Ranging over all values of $r$ and dividing by the total number of possibilities gives us the probability.

$$Pr(\text{no overloaded suit}) = \frac{\sum\limits_{r=0}^{32}\binom{2^7}{r}\binom{2^7-r}{64-2r}\binom{2^{25}}{2}^r(2^{25})^{64-2r}}{\binom{2^{32}}{64}}$$

And so $Pr(\text{at least one overloaded suit}) = 1 - Pr(\text{no overloaded suit})$

This method should be much easier to calculate.

According to Wolfram it turns out $Pr(\text{no overloaded suits})\approx 0.134369$ and so $Pr(\text{at least one overloaded suit})\approx 0.865631$

$\endgroup$
  • $\begingroup$ Nice simpler way to compute with these numbers, taking advantage of the fact $3$ is very small. $\endgroup$ – André Nicolas May 27 '15 at 15:21
  • $\begingroup$ Thank you very much for helping me with this problem! $\endgroup$ – Tomas Vestelind Jun 2 '15 at 14:11

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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