An alternative analysis arriving at the same approximation without the assumption of independence is given by Mitzenmacher and Upfal. After all "n" items have been added to the Bloom filter, let "q" be the fraction of the "m" bits that are set to 0. (That is, the number of bits still set to 0 is "qm".) Then, when testing membership of an element not in the set, for the array position given by any of the "k" hash functions, the probability that the bit is found set to 1 is formula_8. So the probability that all "k" hash functions find their bit set to 1 is formula_9. Further, the expected value of "q" is the probability that a given array position is left untouched by each of the "k" hash functions for each of the "n" items, which is (as above)