Proofs: Bloom filter

The false positive rate of a Bloom filter full

This proof shows: false-positive-rate.

Model. Ideal hashing: the values $h_i(y)$, over all keys $y \in U$ and all $i \in \{1, \ldots, k\}$, are independent and uniform on $\{0, \ldots, m - 1\}$. Insert $n$ distinct keys $S$, and let $x \notin S$. Let $X$ be the number of positions $j$ with $B[j] = 1$, and let $\varepsilon = \Pr[\text{QUERY}(x) = \text{true}]$.

Claim 1 (the exact rate). $\varepsilon = \mathbb{E}[(X/m)^k]$.

Proof. By the correctness proof, $B$ is a function of the $kn$ values $h_i(y)$ for $y \in S$, and QUERY$(x)$ returns true exactly when $B[h_i(x)] = 1$ for each $i$. The $k$ values $h_i(x)$ are independent of the values for $S$, because $x \notin S$, and independent of each other. Given $B$, each $h_i(x)$ hits a 1 bit with probability $X/m$, so the conditional probability that all $k$ hit a 1 bit is $(X/m)^k$. Taking the expectation over $B$ gives the claim. $\square$

Claim 2 (the mean of $X$). $\mathbb{E}[X] = m\left(1 - (1 - 1/m)^{kn}\right)$.

Proof. Position $j$ stays 0 exactly when none of the $kn$ independent values $h_i(y)$, $y \in S$, equals $j$. Each misses $j$ with probability $1 - 1/m$, so position $j$ is 0 with probability $(1 - 1/m)^{kn}$. By linearity of expectation over the $m$ positions, $\mathbb{E}[m - X] = m(1 - 1/m)^{kn}$. $\square$

Claim 3 (the classical formula is a lower bound).

Proof. The function $t \mapsto t^k$ is convex on $[0, 1]$ for $k \ge 1$, so by Jensen's inequality $\mathbb{E}[(X/m)^k] \ge (\mathbb{E}[X]/m)^k$. Claim 2 gives the first inequality. The second follows from $1 - 1/m \le e^{-1/m}$, which makes $1 - (1 - 1/m)^{kn} \ge 1 - e^{-kn/m}$, and from the fact that $t \mapsto t^k$ is increasing on $[0, 1]$. $\square$

Claim 4 (concentration). For each $\lambda > 0$, $\Pr[X \ge \mathbb{E}[X] + \lambda] \le e^{-2\lambda^2/(kn)}$. Hence, with $p = \mathbb{E}[X]/m$,

Proof. $X$ is a function of the $kn$ independent values $h_i(y)$. Changing one of them moves at most one 1 bit, so it changes $X$ by at most 1. The bounded differences inequality (McDiarmid's form of the Azuma inequality) then gives the tail bound. For the second part, split on the event $E = \{X < \mathbb{E}[X] + \lambda\}$. On $E$, $(X/m)^k \le (p + \lambda/m)^k$. Off $E$, $(X/m)^k \le 1$, and $\Pr[\bar E]$ is at most the tail bound. Claim 1 adds the two parts. $\square$

Consequence. Take $\lambda = \sqrt{kn \ln m}$. Then the second term is $m^{-2}$, and $\lambda/m = O(\sqrt{(\log m)/m})$ when $kn = O(m)$. So $\varepsilon = (1 - (1 - 1/m)^{kn})^k + O(k\sqrt{(\log m)/m}) + O(m^{-2})$, and for fixed $k$ and a fixed ratio $m/n$ the rate tends to $(1 - e^{-kn/m})^k$ as $m \to \infty$, since $(1 - 1/m)^{kn} \to e^{-kn/m}$.

Probes of a query. For $x \notin S$, given $B$, the rounds of line L6 look at independent uniform positions, and each one is 0 with probability $1 - X/m$. The loop stops at the first 0 or after $k$ rounds, so the number of rounds is at most a geometric random variable with mean $1/(1 - X/m)$ when $X < m$. $\blacksquare$

A Bloom filter has no false negatives full

This proof shows: correctness, invariant, termination.

Write $B_t$ for the bit array after the first $t$ operations, and $S_t$ for the set of keys inserted by them. The hash functions $h_1, \ldots, h_k$ are fixed by line L2 and do not change. Let $P(x) = \{h_1(x), \ldots, h_k(x)\}$ be the set of positions of a key $x$.

Lemma 1 (bits only rise). For each $t$ and each position $j$, if $B_t[j] = 1$ then $B_{t+1}[j] = 1$.

Proof. A QUERY writes nothing. An INSERT writes only in line L4, and it writes the value 1. So no operation changes a 1 to a 0. $\square$

Lemma 2 (invariant (B)). For each $t$, each $x \in S_t$ and each $j \in P(x)$, $B_t[j] = 1$.

Proof. By induction on $t$. For $t = 0$, line L1 makes all bits 0, and $S_0 = \emptyset$, so the claim holds with nothing to check. Assume the claim for $t$. If operation $t + 1$ is a QUERY, then $S_{t+1} = S_t$ and $B_{t+1} = B_t$, so the claim holds. If it is INSERT$(y)$, then $S_{t+1} = S_t \cup \{y\}$. For $x \in S_t$ and $j \in P(x)$ we have $B_t[j] = 1$ by the hypothesis, so $B_{t+1}[j] = 1$ by Lemma 1. For $x = y$, the loop of lines L3 and L4 runs for $i = 1, \ldots, k$ and sets $B[h_i(y)] = 1$ for each $i$, so each $j \in P(y)$ is 1 after the loop. A later round of the same loop writes only the value 1, so it does not undo an earlier round. $\square$

Theorem. After any sequence of operations, QUERY$(x)$ returns true for each inserted key $x$. If QUERY$(x)$ returns false, then $x$ was never inserted. QUERY$(x)$ returns true exactly when $B[j] = 1$ for each $j \in P(x)$.

Proof. The loop of lines L5 and L6 reads $B[h_i(x)]$ for $i = 1, 2, \ldots$ and returns false at the first $i$ with $B[h_i(x)] = 0$. If there is no such $i$, it ends after $k$ rounds and line L7 returns true. So QUERY returns true exactly when each position of $P(x)$ holds a 1. If $x \in S_t$, Lemma 2 says that each position of $P(x)$ holds a 1, so the query returns true. The second claim is the contrapositive of the first. $\square$

Union. Let $B$ and $B'$ be the arrays for the sets $S$ and $S'$, built with the same $m$ and the same hash functions from an all-zero array. By Lemma 1 and line L4, position $j$ is 1 in $B$ exactly when $j \in \bigcup_{x \in S} P(x)$, because no other position is ever written. So $B[j] \lor B'[j] = 1$ exactly when $j \in \bigcup_{x \in S \cup S'} P(x)$, which is the array that inserting $S \cup S'$ gives.

Termination. Each loop of lines L3 and L5 has at most $k$ rounds, and each round does one hash evaluation and one access to the array. $\blacksquare$