Here’s a derivation of the formula Bose et al give for the false positive probability: To calculate the probability, we will work out the number of ways to ass

Here’s a derivation of the formula Bose et al give for the false positive probability: To calculate the probability, we will work out the number of ways to assign kl hashes to m bits (I.e. functions from a set of size kl to a set of size m), and for each of those ways we will work out how many ways we could assign k hashes to the bits which are set (I.e. ways to get a false positive). We then count the number of possible ways to assign our kl hashes of existing elements and k hashes of the tested element to m bits and divide the former by the latter. For the argument to be valid, each assignment of hashes to bits must have equal probability, which is true if the hashes are independent. The simple way to count the number of assignments of kl hashes to m bits is easy: for each hash there are m possible bits so we get: m^(kl) Similarly for kl + k hashes: m^(k(l + 1)) Now we will break this count up by the number of bits which are set. Suppose i bits are set. Then the number of possibilities for those set bits of the m total bits is (m choose i). And the number of ways the kl hashes could be assigned to the i bits is equal to the number of surjections from a set of kl hashes to a set of i bits, which is i!{kl; i}, where {s; t} is the sterling number of the second kind, the number of ways to partition s labelled objects into t unlabelled non-empty partitions [the author’s paper claims this is the number of surjections which is slightly wrong]. This gives the number of assignments given exactly i set bits as: (m choose i) i! {kl; i} And the total as: m^(kl) = Sum_(i = 0)^m (m choose i) i! {kl; i} Given exactly i bits are set, how many ways can we assign k hashes to those i bits? Easy: i^k. So the number of lists of kl + k hashes (integers from 1 to m) such that the last k all appear in the earlier list of kl is: Sum_i i^k (m choose i) i! {kl; i} Finally we divide by the number of possible lists, m^(k(l+1)), to get the probability given by Bose et al (this is valid because the hashes are iid so each list has equal probability of occurring)