已知m=2n，求布隆过滤器假阳性概率≤1/n的哈希函数数k

Hey there! Let's break down your Bloom Filter problem step by step—first checking your existing derivation, then working through the math to find valid values of k that meet your false positive requirement.

Checking Your Derivation #

First, let's validate the parts you've got so far:

• Your approximation for the probability that a single bit remains 0 is correct:

  Pr(bit = 0) = (1 - 1/m)^{kn} ≈ e^{-kn/m}
  This uses the standard limit approximation (1 - x)^y ≈ e^{-xy} for large m, which is perfectly valid for Bloom Filter calculations.

• Where you went wrong: You wrote Pr(bit = 1) = (1 - e^{-kn/m})^k—this mislabels the expression. The probability that a single bit is 1 is actually Pr(bit = 1) = 1 - Pr(bit = 0) ≈ 1 - e^{-kn/m}. The expression (1 - e^{-kn/m})^k refers to the false positive probability: the chance that an element not in the filter has all k of its hash positions set to 1.

Solving for k to Meet the False Positive Requirement #

You've specified m = 2n and need the false positive probability P ≤ 1/n. Let's substitute m = 2n into the correct false positive formula:

P = (1 - e^{-kn/m})^k = (1 - e^{-k/2})^k

Our goal is to find integer values of k such that this P is at most 1/n.

First, check the optimal k for minimal false positives #

The well-known optimal number of hash functions for a Bloom Filter is k_opt = (m/n) * ln(2). Here, m/n = 2, so k_opt ≈ 2 * 0.693 = 1.386. Since k must be an integer, we test k=1 and k=2 first (these will give the lowest possible false positive probabilities for your m=2n setup):

• For k=1: P ≈ 1 - e^{-0.5} ≈ 0.393
• For k=2: P ≈ (1 - e^{-1})^2 ≈ (0.632)^2 ≈ 0.400

Now we check if these meet P ≤ 1/n:

• If n ≤ 2: 1/n ≥ 0.5, so both k=1 and k=2 satisfy the requirement.
• If n ≥ 3: 1/n ≤ 0.333, but the minimal false positive probability we can get (≈0.393) is larger than 1/n. This means no integer value of k will satisfy your false positive requirement when m=2n and n≥3. The bit array size m=2n is simply too small to achieve a false positive rate as low as 1/n for larger n.

Theoretical non-integer k (for completeness) #

If we ignore the integer constraint for k, we can set up the inequality:

(1 - e^{-k/2})^k ≤ 1/n

Taking the natural logarithm of both sides (logarithms preserve inequalities here since all terms are positive):

k * ln(1 - e^{-k/2}) ≤ -ln(n)

This equation doesn't have a closed-form solution, but numerical methods confirm that even for non-integer k, the minimal value of the left-hand side is ≈-0.938 (at k≈1.386), which translates to n ≤ e^{0.938} ≈ 2.55. So even in theory, no k can meet the requirement for n>2.

内容的提问来源于stack exchange，提问作者Razor