# Heuristic analysis of Bloom filters

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?

## 1 Answer

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|}$.

• 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. – FrostyStraw Nov 19 '16 at 6:23
• If a bit hasn't been hit then it's zero. The probability you keep repeating is that of a zero bit. – Yuval Filmus Nov 19 '16 at 6:43
• 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? – FrostyStraw Nov 19 '16 at 7:16
• 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. – Yuval Filmus Nov 19 '16 at 7:56
• 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. – FrostyStraw Nov 19 '16 at 16:38