FAILURE MAP
← Case archive

FA-72896 / Probabilistic sketches / Open access

Bloom filter sizing: predicted false-positive rate uses inverted load · case 01

The reported false-positive rate is far too optimistic.

Verified by executionVariant 1 · 10 checks per implementationDownload source bundle ↓JSON ↗

ROOT CAUSE

The exponent uses k*m/n instead of k*n/m for the probability that a bit remains zero.

VERIFIED REPAIR

Use exp(-k n / m) as the probability that a bit is still clear.

Unsuccessful approach: Dropping k from the exponent treats the filter as if each item set a single bit.

Case contract

Input {n, p}. Reject n <= 0 or p outside the open interval (0,1) with "invalid". Otherwise m = ceil(-n ln p / (ln 2)^2), k = max(1, round(m/n * ln 2)), bytes = ceil(m/8), and the predicted false-positive rate (1 - e^(-k n / m))^k rounded to 6 decimals. Return [m, k, bytes, fp].

Why this case matters

Capacity planning for a Bloom filter decides memory and probe count before any item is inserted; an undersized array silently exceeds the promised false-positive rate.

1 / The failure

Exit 1
"""Failure Map reference implementation. Python standard library only."""
import json
import math
N = 1
observations = []
def solve(x):
    n = x['n']
    p = x['p']
    if n <= 0 or not (0 < p < 1):
        return 'invalid'
    m = math.ceil(-n * math.log(p) / (math.log(2) ** 2))
    k = max(1, round(m / n * math.log(2)))
    fp = (1 - math.exp(-k * m / n)) ** k
    return [m, k, (m + 7) // 8, round(fp, 6)]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['thousand items one percent', {'n': 1007, 'p': 0.01}, [9653, 7, 1207, 0.010035]],
  ['small set loose target', {'n': 4, 'p': 0.3}, [11, 2, 2, 0.267056]],
  ['near-one target clamps probes', {'n': 50, 'p': 0.9}, [11, 1, 2, 0.989385]],
  ['tight target', {'n': 201, 'p': 0.0001}, [3854, 13, 482, 0.0001]],
  ['odd bit count', {'n': 38, 'p': 0.05}, [237, 4, 30, 0.050232]],
  ['medium set', {'n': 17, 'p': 0.02}, [139, 6, 18, 0.019754]],
  ['rejects p equal one', {'n': 10, 'p': 1.0}, 'invalid'],
  ['rejects empty set', {'n': 0, 'p': 0.01}, 'invalid'],
  ['another sizing', {'n': 780, 'p': 0.123}, [3403, 3, 426, 0.122936]],
  ['fractional ceil', {'n': 10, 'p': 0.07}, [56, 4, 7, 0.067896]]],
 [['thousand items one percent', {'n': 1014, 'p': 0.01}, [9720, 7, 1215, 0.010036]],
  ['small set loose target', {'n': 5, 'p': 0.3}, [13, 2, 2, 0.287972]],
  ['near-one target clamps probes', {'n': 100, 'p': 0.9}, [22, 1, 3, 0.989385]],
  ['tight target', {'n': 202, 'p': 0.0001}, [3873, 13, 485, 0.0001]],
  ['odd bit count', {'n': 39, 'p': 0.05}, [244, 4, 31, 0.049785]],
  ['medium set', {'n': 22, 'p': 0.02}, [180, 6, 23, 0.019701]],
  ['rejects p equal one', {'n': 10, 'p': 1.0}, 'invalid'],
  ['rejects empty set', {'n': 0, 'p': 0.01}, 'invalid'],
  ['another sizing', {'n': 783, 'p': 0.123}, [3416, 3, 427, 0.122943]],
  ['fractional ceil', {'n': 11, 'p': 0.07}, [61, 4, 8, 0.069737]]],
 [['thousand items one percent', {'n': 1021, 'p': 0.01}, [9787, 7, 1224, 0.010036]],
  ['small set loose target', {'n': 6, 'p': 0.3}, [16, 2, 2, 0.278397]],
  ['near-one target clamps probes', {'n': 150, 'p': 0.9}, [33, 1, 5, 0.989385]],
  ['tight target', {'n': 203, 'p': 0.0001}, [3892, 13, 487, 0.0001]],
  ['odd bit count', {'n': 40, 'p': 0.05}, [250, 4, 32, 0.049931]],
  ['medium set', {'n': 27, 'p': 0.02}, [220, 6, 28, 0.020034]],
  ['rejects p equal one', {'n': 10, 'p': 1.0}, 'invalid'],
  ['rejects empty set', {'n': 0, 'p': 0.01}, 'invalid'],
  ['another sizing', {'n': 786, 'p': 0.123}, [3429, 3, 429, 0.122949]],
  ['fractional ceil', {'n': 12, 'p': 0.07}, [67, 4, 9, 0.068452]]],
 [['thousand items one percent', {'n': 1028, 'p': 0.01}, [9854, 7, 1232, 0.010037]],
  ['small set loose target', {'n': 7, 'p': 0.3}, [18, 2, 3, 0.29222]],
  ['near-one target clamps probes', {'n': 200, 'p': 0.9}, [44, 1, 6, 0.989385]],
  ['tight target', {'n': 204, 'p': 0.0001}, [3911, 13, 489, 0.0001]],
  ['odd bit count', {'n': 41, 'p': 0.05}, [256, 4, 32, 0.05007]],
  ['medium set', {'n': 32, 'p': 0.02}, [261, 6, 33, 0.019953]],
  ['rejects p equal one', {'n': 10, 'p': 1.0}, 'invalid'],
  ['rejects empty set', {'n': 0, 'p': 0.01}, 'invalid'],
  ['another sizing', {'n': 789, 'p': 0.123}, [3442, 3, 431, 0.122956]],
  ['fractional ceil', {'n': 13, 'p': 0.07}, [72, 4, 9, 0.069978]]],
 [['thousand items one percent', {'n': 1035, 'p': 0.01}, [9921, 7, 1241, 0.010037]],
  ['small set loose target', {'n': 8, 'p': 0.3}, [21, 2, 3, 0.284327]],
  ['near-one target clamps probes', {'n': 250, 'p': 0.9}, [55, 1, 7, 0.989385]],
  ['tight target', {'n': 205, 'p': 0.0001}, [3930, 13, 492, 0.0001]],
  ['odd bit count', {'n': 42, 'p': 0.05}, [262, 4, 33, 0.050203]],
  ['medium set', {'n': 37, 'p': 0.02}, [302, 6, 38, 0.019895]],
  ['rejects p equal one', {'n': 10, 'p': 1.0}, 'invalid'],
  ['rejects empty set', {'n': 0, 'p': 0.01}, 'invalid'],
  ['another sizing', {'n': 792, 'p': 0.123}, [3455, 3, 432, 0.122963]],
  ['fractional ceil', {'n': 14, 'p': 0.07}, [78, 4, 10, 0.068853]]]]
for label, args, expected in cases[N - 1]:
    check(label, solve(args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)
Boundary fixtureActualExpectedOutcome
thousand items one percent[9653, 7, 1207, 1.0][9653, 7, 1207, 0.010035]Failed
small set loose target[11, 2, 2, 0.991843][11, 2, 2, 0.267056]Failed
near-one target clamps probes[11, 1, 2, 0.197481][11, 1, 2, 0.989385]Failed
tight target[3854, 13, 482, 1.0][3854, 13, 482, 0.0001]Failed
odd bit count[237, 4, 30, 1.0][237, 4, 30, 0.050232]Failed
medium set[139, 6, 18, 1.0][139, 6, 18, 0.019754]Failed
rejects p equal oneinvalidinvalidPassed
rejects empty setinvalidinvalidPassed
another sizing[3403, 3, 426, 0.999994][3403, 3, 426, 0.122936]Failed
fractional ceil[56, 4, 7, 1.0][56, 4, 7, 0.067896]Failed

SHA-256 / 103163be8010b7f856a56d5d52cfa3833429530ec851c8d92b78d4ce78e69f9e

2 / The unsuccessful fix

Exit 1
"""Failure Map reference implementation. Python standard library only."""
import json
import math
N = 1
observations = []
def solve(x):
    n = x['n']
    p = x['p']
    if n <= 0 or not (0 < p < 1):
        return 'invalid'
    m = math.ceil(-n * math.log(p) / (math.log(2) ** 2))
    k = max(1, round(m / n * math.log(2)))
    fp = (1 - math.exp(-n / m)) ** k
    return [m, k, (m + 7) // 8, round(fp, 6)]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['thousand items one percent', {'n': 1007, 'p': 0.01}, [9653, 7, 1207, 0.010035]],
  ['small set loose target', {'n': 4, 'p': 0.3}, [11, 2, 2, 0.267056]],
  ['near-one target clamps probes', {'n': 50, 'p': 0.9}, [11, 1, 2, 0.989385]],
  ['tight target', {'n': 201, 'p': 0.0001}, [3854, 13, 482, 0.0001]],
  ['odd bit count', {'n': 38, 'p': 0.05}, [237, 4, 30, 0.050232]],
  ['medium set', {'n': 17, 'p': 0.02}, [139, 6, 18, 0.019754]],
  ['rejects p equal one', {'n': 10, 'p': 1.0}, 'invalid'],
  ['rejects empty set', {'n': 0, 'p': 0.01}, 'invalid'],
  ['another sizing', {'n': 780, 'p': 0.123}, [3403, 3, 426, 0.122936]],
  ['fractional ceil', {'n': 10, 'p': 0.07}, [56, 4, 7, 0.067896]]],
 [['thousand items one percent', {'n': 1014, 'p': 0.01}, [9720, 7, 1215, 0.010036]],
  ['small set loose target', {'n': 5, 'p': 0.3}, [13, 2, 2, 0.287972]],
  ['near-one target clamps probes', {'n': 100, 'p': 0.9}, [22, 1, 3, 0.989385]],
  ['tight target', {'n': 202, 'p': 0.0001}, [3873, 13, 485, 0.0001]],
  ['odd bit count', {'n': 39, 'p': 0.05}, [244, 4, 31, 0.049785]],
  ['medium set', {'n': 22, 'p': 0.02}, [180, 6, 23, 0.019701]],
  ['rejects p equal one', {'n': 10, 'p': 1.0}, 'invalid'],
  ['rejects empty set', {'n': 0, 'p': 0.01}, 'invalid'],
  ['another sizing', {'n': 783, 'p': 0.123}, [3416, 3, 427, 0.122943]],
  ['fractional ceil', {'n': 11, 'p': 0.07}, [61, 4, 8, 0.069737]]],
 [['thousand items one percent', {'n': 1021, 'p': 0.01}, [9787, 7, 1224, 0.010036]],
  ['small set loose target', {'n': 6, 'p': 0.3}, [16, 2, 2, 0.278397]],
  ['near-one target clamps probes', {'n': 150, 'p': 0.9}, [33, 1, 5, 0.989385]],
  ['tight target', {'n': 203, 'p': 0.0001}, [3892, 13, 487, 0.0001]],
  ['odd bit count', {'n': 40, 'p': 0.05}, [250, 4, 32, 0.049931]],
  ['medium set', {'n': 27, 'p': 0.02}, [220, 6, 28, 0.020034]],
  ['rejects p equal one', {'n': 10, 'p': 1.0}, 'invalid'],
  ['rejects empty set', {'n': 0, 'p': 0.01}, 'invalid'],
  ['another sizing', {'n': 786, 'p': 0.123}, [3429, 3, 429, 0.122949]],
  ['fractional ceil', {'n': 12, 'p': 0.07}, [67, 4, 9, 0.068452]]],
 [['thousand items one percent', {'n': 1028, 'p': 0.01}, [9854, 7, 1232, 0.010037]],
  ['small set loose target', {'n': 7, 'p': 0.3}, [18, 2, 3, 0.29222]],
  ['near-one target clamps probes', {'n': 200, 'p': 0.9}, [44, 1, 6, 0.989385]],
  ['tight target', {'n': 204, 'p': 0.0001}, [3911, 13, 489, 0.0001]],
  ['odd bit count', {'n': 41, 'p': 0.05}, [256, 4, 32, 0.05007]],
  ['medium set', {'n': 32, 'p': 0.02}, [261, 6, 33, 0.019953]],
  ['rejects p equal one', {'n': 10, 'p': 1.0}, 'invalid'],
  ['rejects empty set', {'n': 0, 'p': 0.01}, 'invalid'],
  ['another sizing', {'n': 789, 'p': 0.123}, [3442, 3, 431, 0.122956]],
  ['fractional ceil', {'n': 13, 'p': 0.07}, [72, 4, 9, 0.069978]]],
 [['thousand items one percent', {'n': 1035, 'p': 0.01}, [9921, 7, 1241, 0.010037]],
  ['small set loose target', {'n': 8, 'p': 0.3}, [21, 2, 3, 0.284327]],
  ['near-one target clamps probes', {'n': 250, 'p': 0.9}, [55, 1, 7, 0.989385]],
  ['tight target', {'n': 205, 'p': 0.0001}, [3930, 13, 492, 0.0001]],
  ['odd bit count', {'n': 42, 'p': 0.05}, [262, 4, 33, 0.050203]],
  ['medium set', {'n': 37, 'p': 0.02}, [302, 6, 38, 0.019895]],
  ['rejects p equal one', {'n': 10, 'p': 1.0}, 'invalid'],
  ['rejects empty set', {'n': 0, 'p': 0.01}, 'invalid'],
  ['another sizing', {'n': 792, 'p': 0.123}, [3455, 3, 432, 0.122963]],
  ['fractional ceil', {'n': 14, 'p': 0.07}, [78, 4, 10, 0.068853]]]]
for label, args, expected in cases[N - 1]:
    check(label, solve(args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)
Boundary fixtureActualExpectedOutcome
thousand items one percent[9653, 7, 1207, 0.0][9653, 7, 1207, 0.010035]Failed
small set loose target[11, 2, 2, 0.092937][11, 2, 2, 0.267056]Failed
near-one target clamps probes[11, 1, 2, 0.989385][11, 1, 2, 0.989385]Passed
tight target[3854, 13, 482, 0.0][3854, 13, 482, 0.0001]Failed
odd bit count[237, 4, 30, 0.000482][237, 4, 30, 0.050232]Failed
medium set[139, 6, 18, 2e-06][139, 6, 18, 0.019754]Failed
rejects p equal oneinvalidinvalidPassed
rejects empty setinvalidinvalidPassed
another sizing[3403, 3, 426, 0.008595][3403, 3, 426, 0.122936]Failed
fractional ceil[56, 4, 7, 0.000715][56, 4, 7, 0.067896]Failed

SHA-256 / 0a6ccda78e052b478e74121f2109fcb322c08c746ed469b8d03b4cece1f8d131

3 / The verified repair

Exit 0
"""Failure Map reference implementation. Python standard library only."""
import json
import math
N = 1
observations = []
def solve(x):
    n = x['n']
    p = x['p']
    if n <= 0 or not (0 < p < 1):
        return 'invalid'
    m = math.ceil(-n * math.log(p) / (math.log(2) ** 2))
    k = max(1, round(m / n * math.log(2)))
    fp = (1 - math.exp(-k * n / m)) ** k
    return [m, k, (m + 7) // 8, round(fp, 6)]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['thousand items one percent', {'n': 1007, 'p': 0.01}, [9653, 7, 1207, 0.010035]],
  ['small set loose target', {'n': 4, 'p': 0.3}, [11, 2, 2, 0.267056]],
  ['near-one target clamps probes', {'n': 50, 'p': 0.9}, [11, 1, 2, 0.989385]],
  ['tight target', {'n': 201, 'p': 0.0001}, [3854, 13, 482, 0.0001]],
  ['odd bit count', {'n': 38, 'p': 0.05}, [237, 4, 30, 0.050232]],
  ['medium set', {'n': 17, 'p': 0.02}, [139, 6, 18, 0.019754]],
  ['rejects p equal one', {'n': 10, 'p': 1.0}, 'invalid'],
  ['rejects empty set', {'n': 0, 'p': 0.01}, 'invalid'],
  ['another sizing', {'n': 780, 'p': 0.123}, [3403, 3, 426, 0.122936]],
  ['fractional ceil', {'n': 10, 'p': 0.07}, [56, 4, 7, 0.067896]]],
 [['thousand items one percent', {'n': 1014, 'p': 0.01}, [9720, 7, 1215, 0.010036]],
  ['small set loose target', {'n': 5, 'p': 0.3}, [13, 2, 2, 0.287972]],
  ['near-one target clamps probes', {'n': 100, 'p': 0.9}, [22, 1, 3, 0.989385]],
  ['tight target', {'n': 202, 'p': 0.0001}, [3873, 13, 485, 0.0001]],
  ['odd bit count', {'n': 39, 'p': 0.05}, [244, 4, 31, 0.049785]],
  ['medium set', {'n': 22, 'p': 0.02}, [180, 6, 23, 0.019701]],
  ['rejects p equal one', {'n': 10, 'p': 1.0}, 'invalid'],
  ['rejects empty set', {'n': 0, 'p': 0.01}, 'invalid'],
  ['another sizing', {'n': 783, 'p': 0.123}, [3416, 3, 427, 0.122943]],
  ['fractional ceil', {'n': 11, 'p': 0.07}, [61, 4, 8, 0.069737]]],
 [['thousand items one percent', {'n': 1021, 'p': 0.01}, [9787, 7, 1224, 0.010036]],
  ['small set loose target', {'n': 6, 'p': 0.3}, [16, 2, 2, 0.278397]],
  ['near-one target clamps probes', {'n': 150, 'p': 0.9}, [33, 1, 5, 0.989385]],
  ['tight target', {'n': 203, 'p': 0.0001}, [3892, 13, 487, 0.0001]],
  ['odd bit count', {'n': 40, 'p': 0.05}, [250, 4, 32, 0.049931]],
  ['medium set', {'n': 27, 'p': 0.02}, [220, 6, 28, 0.020034]],
  ['rejects p equal one', {'n': 10, 'p': 1.0}, 'invalid'],
  ['rejects empty set', {'n': 0, 'p': 0.01}, 'invalid'],
  ['another sizing', {'n': 786, 'p': 0.123}, [3429, 3, 429, 0.122949]],
  ['fractional ceil', {'n': 12, 'p': 0.07}, [67, 4, 9, 0.068452]]],
 [['thousand items one percent', {'n': 1028, 'p': 0.01}, [9854, 7, 1232, 0.010037]],
  ['small set loose target', {'n': 7, 'p': 0.3}, [18, 2, 3, 0.29222]],
  ['near-one target clamps probes', {'n': 200, 'p': 0.9}, [44, 1, 6, 0.989385]],
  ['tight target', {'n': 204, 'p': 0.0001}, [3911, 13, 489, 0.0001]],
  ['odd bit count', {'n': 41, 'p': 0.05}, [256, 4, 32, 0.05007]],
  ['medium set', {'n': 32, 'p': 0.02}, [261, 6, 33, 0.019953]],
  ['rejects p equal one', {'n': 10, 'p': 1.0}, 'invalid'],
  ['rejects empty set', {'n': 0, 'p': 0.01}, 'invalid'],
  ['another sizing', {'n': 789, 'p': 0.123}, [3442, 3, 431, 0.122956]],
  ['fractional ceil', {'n': 13, 'p': 0.07}, [72, 4, 9, 0.069978]]],
 [['thousand items one percent', {'n': 1035, 'p': 0.01}, [9921, 7, 1241, 0.010037]],
  ['small set loose target', {'n': 8, 'p': 0.3}, [21, 2, 3, 0.284327]],
  ['near-one target clamps probes', {'n': 250, 'p': 0.9}, [55, 1, 7, 0.989385]],
  ['tight target', {'n': 205, 'p': 0.0001}, [3930, 13, 492, 0.0001]],
  ['odd bit count', {'n': 42, 'p': 0.05}, [262, 4, 33, 0.050203]],
  ['medium set', {'n': 37, 'p': 0.02}, [302, 6, 38, 0.019895]],
  ['rejects p equal one', {'n': 10, 'p': 1.0}, 'invalid'],
  ['rejects empty set', {'n': 0, 'p': 0.01}, 'invalid'],
  ['another sizing', {'n': 792, 'p': 0.123}, [3455, 3, 432, 0.122963]],
  ['fractional ceil', {'n': 14, 'p': 0.07}, [78, 4, 10, 0.068853]]]]
for label, args, expected in cases[N - 1]:
    check(label, solve(args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)
Boundary fixtureActualExpectedOutcome
thousand items one percent[9653, 7, 1207, 0.010035][9653, 7, 1207, 0.010035]Passed
small set loose target[11, 2, 2, 0.267056][11, 2, 2, 0.267056]Passed
near-one target clamps probes[11, 1, 2, 0.989385][11, 1, 2, 0.989385]Passed
tight target[3854, 13, 482, 0.0001][3854, 13, 482, 0.0001]Passed
odd bit count[237, 4, 30, 0.050232][237, 4, 30, 0.050232]Passed
medium set[139, 6, 18, 0.019754][139, 6, 18, 0.019754]Passed
rejects p equal oneinvalidinvalidPassed
rejects empty setinvalidinvalidPassed
another sizing[3403, 3, 426, 0.122936][3403, 3, 426, 0.122936]Passed
fractional ceil[56, 4, 7, 0.067896][56, 4, 7, 0.067896]Passed

SHA-256 / a5d0b72374021fa1a7bdf4706b21b106103cbc81777ec03678c8ed05a011ec8f

Verification & scope

A deterministic, bounded teaching model with stipulated constants and pre-hashed or explicitly hashed inputs; it is not a production implementation and makes no claim of conformance to any library or paper beyond the stated contract. This reproducer isolates one failure mechanism. Results cover the supplied fixtures. Variants within a family share a test contract and should remain grouped when constructing evaluation splits. Related mechanisms with a shared evaluation_group must also remain together; these controlled models are not independent production incidents.

Observations recorded using Python 3.12.14 at 2026-09-29T14:48:42.568087+00:00.

Case digest / e36e1ad43c194c4e32cda4213294be4d714103263bfdf5d9c12062b6ff5c3352