hamming distance of bloom filters
Let $S,T$ be two sets of size $n$.  Suppose we hash each to a $m$-bit Bloom filter, using $k$ hash functions; let $x_S$ be the $m$-bit vector corresponding to $S$, and $x_T$ the $m$-bit vector corresponding to $T$.

If $S,T$ agree in a $p$ fraction of entries (i.e., $|S \cap T|=pn$), then 
the expected value of the Hamming distance between these two bit-vectors is

$$\mathbb{E}[d(x_S,x_T)] \approx 2 \exp\{-kn/m\} \times (1 - \exp\{-k(1-p)n/m\}).$$

This gives a relation between the similarity of the two sets (in terms of the number of elements they have in common) and the Hamming distance between their Bloom filters.  In particular: the greater their similarity, the smaller the (expected) Hamming distance between their Bloom filters.



Derivation and details

Where did I get this expression for the expected value of the Hamming distance from from?  Well, consider the $i$th bit of $x_S$.  The probability that this is 0 is

$$\Pr[x_S[i]=0] = \left( 1 - {1 \over m} \right)^{kn}.$$

For the corresponding bit of $x_T$, the probability it is 1 is

$$\Pr[x_T[i]=1] = 1 - \left( 1 - {1 \over m} \right)^{kn}.$$

How about the conjunction of these two events, i.e., that $x_S[i]=0$ and $x_T[i]=1$?  We can't just multiply the two probabilities, because the two events aren't independent: the $pn$ elements in $S \cap T$ will certainly hash to the same place.  However, we can take that into account by expressing the probability as

$$\Pr[x_S[i]=0 \land x_T[i]=1] = q_1 \times q_2 \times q_3$$

where $q_1$ is the probability that none of the elements of $S \setminus T$ hash to position $i$ (i.e., $\Pr[x_{S \setminus T}[i]=0]$); $q_2$ is the probability that none of the elements of $S \cap T$ hash to position $i$ (i.e., $\Pr[x_{S \cap T}[i]=0]$); and $q_3$ is the probability that at least one of the elements of $T \setminus S$ hashes to position $i$ (i.e., $\Pr[x_{T \setminus S}[i]=1]$).  Each of these can be computed as

$$\begin{align*}
q_1 &amp;= \left(1 - {1 \over m}\right)^{k \cdot |S \setminus T|} = \left(1 - {1 \over m}\right)^{k(1-p)n}\\
q_2 &amp;= \left(1 - {1 \over m}\right)^{k \cdot |S \cap T|} = \left(1 - {1 \over m}\right)^{kpn}\\
q_3 &amp;= 1 - \left(1 - {1 \over m}\right)^{k \cdot |T \setminus S|} = 1 - \left(1 - {1 \over m}\right)^{k(1-p)n}.
\end{align*}$$

Therefore, multiplying these quantities, we find that

$$\Pr[x_S[i]=0 \land x_T[i]=1] =
\left(1 - {1 \over m}\right)^{kn} \times \left(1 - \left(1 - {1 \over m}\right)^{k(1-p)n} \right).$$

Using the approximation $(1 - 1/m)^t \approx e^{-t/m}$, we see that

$$\Pr[x_S[i]=0 \land x_T[i]=1] \approx
\exp\{-kn/m\} \times (1 - \exp\{-k(1-p)n/m\}).$$

Now by symmetry,

$$\begin{align*}
\Pr[x_S[i] \ne x_T[i]]
 &amp;= \Pr[x_S[i]=0 \land x_T[i]=1] + \Pr[x_S[i]=1 \land x_T[i]=0]\\
 &amp;\approx 2 \exp\{-kn/m\} \times (1 - \exp\{-k(1-p)n/m\}).
\end{align*}$$

Finally, linearity of expectation tells us that the expected Hamming distance between $x_S$ and $x_T$ is $m$ times the above quantity.