1
$\begingroup$

I'm attempting a question related to Bloom filters:

Our Bloom filter uses $3$ different independent hash functions $H_1, H_2, H_3$ that each take any string as input and each return an index into a bit-array of length $n$. Each index is equally likely for each hash function.

To add a string into the set, feed it to each of the $3$ hash functions to get $3$ array positions. Set the bits at all these positions to $1$. For example, initially all values in the bit-array are zero. In this example $n = 10$:

Index: 0 1 2 3 4 5 6 7 8 9
Value: 0 0 0 0 0 0 0 0 0 0

After adding the string "word", where $H_1($"word"$)=4$, $H_2($"word"$)=7$ and $H_3($"word"$)=8$:

Index: 0 1 2 3 4 5 6 7 8 9
Value: 0 0 0 0 1 0 0 1 1 0

Bits are never switched back to $0$. Consider a Bloom filter with $n=9000$ buckets. You have added $m=1000$ strings to the filter.

a) What is the probability that the first bucket has $0$ strings hashed to it?

b) To check whether a string is in the set, feed it to each of the $3$ hash functions to get $3$ array positions. If any of the bits at these positions is $0$, the element is not in the set. If all bits at these positions are $1$, the string may be in the set; but it could be that those bits are $1$ because some of the other strings hashed to the same values. You may assume that the value of one bucket is independent of the value of all others.

What is the probability that a string which has not previously been added to the set will be misidentified as in the set. That is, what is the probability that the bits at all of its hash positions are already $1$?

For the first part, probability that a certain string is not hashed by $H_1$ to first bucket is $8999/9000$. Probability that that string isn't hashed by any of the $3$ functions is therefore $(8999/9000)^3$. Probability that none of the strings is hashed by any of the hashing functions to the first bucket is then $(8999/9000)^{3000}$.

I hope so far I'm going on the right track. I'm completely confused by the second part though. Am I supposed to use some specific probability distribution for this?

Edit: after Yuval's comment, here's an attempt at the second part: We're supposed to find the probability that $3$ specific buckets (say buckets no. $p,q,r$) already have a string hashed to them. This is

$$P(p=1,q=1,r=1)=1-P((p=0)\cup(q=0)\cup(r=0))$$

The union can be calculated as (denoting events $p=0, q=0, r=0$ as $p_0, q_0, r_0$ respectively)

$$P(p_0\cup q_0\cup r_0)=\\P(p_0)+P(q_0)+P(r_0)-P(p_0,q_0)-P(q_0,r_0)-P(r_0,p_0)+P(p_0,q_0,r_0)$$

$P(p_0),P(q_0),P(r_0)$ will be the same as the answer to the first question. $P(p_0,q_0)$ will be (using similar logic as in part a) $\big(\frac{8998}{9000}\big)^{3000}$. $P(p_0,q_0,r_0)$ will be $\big(\frac{8997}{9000}\big)^{3000}$. Plugging all these values in, we get the answer.

Is this okay?

$\endgroup$
  • $\begingroup$ You throw 3000 balls to 9000 buckets. Then you throw another 3 balls. What is the probability that all the buckets they fall into are non-empty? $\endgroup$ – Yuval Filmus Oct 12 at 17:43
  • $\begingroup$ @YuvalFilmus: I realize that the scenario you mentioned is equivalent, but I'm still not sure how to go about solving that. I can't assume that the events of any of the buckets being non-empty are independent, so I'm at a loss $\endgroup$ – yee Oct 12 at 18:24
  • $\begingroup$ Could you do it if the last 3 balls fall into different buckets? You can reduce to such calculations. To do each calculation, use inclusion-exclusion. $\endgroup$ – Yuval Filmus Oct 12 at 18:29
  • $\begingroup$ @YuvalFilmus: Based on your comment, I've edited the question to include my latest attempt. Is that okay? $\endgroup$ – yee Oct 12 at 18:34
  • $\begingroup$ You also need to take into account the possibility that some of $p,q,r$ are equal. $\endgroup$ – Yuval Filmus Oct 12 at 19:45

Your Answer

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

Browse other questions tagged or ask your own question.