2
$\begingroup$

I am currently watching a lecture on Bloom filters, and the professor is doing a heuristic analysis of Bloom filters.

It's all based on the following assumption:

All $h_{i}(x)$'s are uniformly random and independent (across different $i$'s and $x$'s)

Setup:

  • Bloom filter of length $n$ bits.
  • Data set $S$ is inserted into the Bloom filters.

The professors claims that for each bit of array $A$, the probability that it has been set to 1 is (under above assumption, and after data set has been inserted): $1 - (1 - 1/n)^{k|S|}$, where $k$ is the number of hash functions.

I am trying to understand why that's the probability.

He explains that as each of the $|S|$ objects gets inserted (0 or 1), there are $k$ "darts" thrown uniformly at random and independent from each other thrown into the array, so that gives me the intuition of why $k$ is being multiplied by $|S|$. He then says the probability that a given "dart" is one of the $n$ bits is $1/n$. Since there are a total of $k|S|$ "darts" thrown at the end, it makes sense that after the whole set $S$ has been inserted, the probability that a given bit has been hit is $(1/n)^{k|S|}$, and the probability that it hasn't been hit is $(1-1/n)^{k|S|}$. But I don't understand why all that is being subtracted from $1$ at the end to end up being $1 - (1 - 1/n)^{k|S|}$, so clearly I'm missing something...

Can somebody explain this to me?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

A bit is set to 1 if it has been hit. It has $k|S|$ chances of being hit, and each time it is hit with probability $1/n$. Using a union bound, the probability that a bit is hit is at most $k|S|/n$.

We can improve on this bound by calculating instead the probability that a bit is 0, that is, that it is not hit. For a bit not to be hit, it has to be missed each time. Since it has $k|S|$ opportunities to be hit, and each time it is missed with probability $1-1/n$, in total a bit is missed with probability $(1-1/n)^{k|S|}$. Thus a bit is not missed with probability $1-(1-1/n)^{k|S|}$.

Improve this answer
$\endgroup$
5
  • $\begingroup$ But..but..We got that the probability that a bit hasn't been hit (1 - 1/n)^(k|S|) from the knowledge that the probability that any given bit was "hit by a dart" was 1/n. Since there are k "darts" thrown per |S| object, that would lead me to think that the probability that any given bit was set to 1 to be (1/n)^(k|S|), and that the analysis would end there. $\endgroup$
    – FrostyStraw
    Nov 19, 2016 at 6:23
  • $\begingroup$ If a bit hasn't been hit then it's zero. The probability you keep repeating is that of a zero bit. $\endgroup$
    – Yuval Filmus
    Nov 19, 2016 at 6:43
  • $\begingroup$ I am so lost. I'm not sure which probability you say that I'm repeating. I am still not understanding why the answer isn't simply (1/n)^(k|S|). If our job was to just choose one random bit to set to 1, the probability of any random bit being set to 1 is 1/n. But since we are doing this k|S| times, it makes sense that it's 1/n^(k|S|). Where am I going wrong with my logic? $\endgroup$
    – FrostyStraw
    Nov 19, 2016 at 7:16
  • $\begingroup$ Actually, $1/n^{k|S|}$ is the probability that the bit is hit every time. We want to know the probability that it is hit at least once, which is much higher. $\endgroup$
    – Yuval Filmus
    Nov 19, 2016 at 7:56
  • $\begingroup$ Yeah, I think I understand it now. I just had trouble differentiating between a bit being hit a particular time and a bit being hit after the whole set S has been inserted. (1 - 1/n)^(k|S|) is the probability that a particular bit is NEVER hit, so if we subtract this probability from 1, we get the probability that it is hit at least once. $\endgroup$
    – FrostyStraw
    Nov 19, 2016 at 16:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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