# Math in Bloom Filter

Bloom filter is building block for various applications.

## What is Bloom filter (BF)?

Bloom filter is a data structure for probabilistic set membership detection.

Here is a definition.

Bloom Filter BF could be an array of length $$m$$ 01 bit, which can represent a set $$A$$ with $$n$$ elements.
$A = {a_1, a_2, \cdots, a_n}$
Reader may ask how we gonna put those elements into such an array. The answer is hashing. Along with this array, a BF usually has $$k$$ independent hash functions. The basic idea of BF is that to allocate an element $$a_i$$ in $$A$$, we will calculate $$h_1(a_i),h_2(a_i),\cdots,h_k(a_i)$$ and then set $$BF_{A}[h(a)]$$ to 1.

## How to check set membership?

To check if an element $$a_x$$ is in the set $$A$$, $$a_x$$ is hashed by $$k$$ hash functions， if for every hash result, $$BF [h(a_x)]$$ is 1, then this element has a great probability in the set.
On the contrary, if any $$BF [h(a_x)]$$ is 0, then we have probability as 1 for sure that this element is not in the set.

## What is the probability that a bit in BF is 1?

To figure out this, first, to figure out the game rule, it is like pour water in bottle. Every time you pick up a bottle by the hash, you need pour some water into this bottle. For a particular bottle, the chance it is non-empty for one hash is $$1-\frac{1}{m}$$. After we finish one element, it is in total $$k$$ round. so the probability that one particular bit is not set as 1 during one element is $$(1-\frac{1}{m})^{k}$$. Since we have $$n$$ elements in the set, after we process all those elements, this probability that one particular bit is set to 1 should be
$1-(1-\frac{1}{m})^{kn}$

## What is the upper bound of false positive probability?

As mentioned, BF is a probabilistic membership checking method. False positive probability is the probability that you get a resulting indicating that one element is in the set but the actual result is that this element is not in the set. So it is a false alarm. To calculate this probability, we will refer to a paper and learn from it.
(To Be Continued.)