Bloom Filters and False Positives

• Suppose you are given a Bloom Filter with 3 hash functions h1, h2, h3, and m indices.
• At the moment, exactly 2m/3 indices are set to true, while the remaining m/3 are set to false. You are safe to assume that m is divisible by 3.

• You may also assume that the three hash functions are universal and independent such that:

  1. The probability that hi(x)=p is exactly 1/m for all indices p and (i=1,2,3)
  2. hi(x) is independent of hj(y), for all i, j ∈ {1,2,3} and x,y when i does not equal y.

Answer the following and explain: If you search for 27 items, none of which are inside the Bloom filter, how many false positives will you get on average? Thanks