FA-72871 / Probabilistic sketches / Open access

Bloom filter sizing: bit count rounds down · case 01

The allocated bit array is one bit short and the realised false-positive rate exceeds the target.

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

ROOT CAUSE

The bit count truncates -n ln p/(ln 2)^2 instead of taking its ceiling.

VERIFIED REPAIR

Take the ceiling of the fractional bit count.

Unsuccessful approach: Rounding to nearest still under-allocates whenever the fractional part is below one half.

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 = int(-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 fixture	Actual	Expected	Outcome
thousand items one percent	`[9652, 7, 1207, 0.01004]`	`[9653, 7, 1207, 0.010035]`	Failed
small set loose target	`[10, 2, 2, 0.303239]`	`[11, 2, 2, 0.267056]`	Failed
near-one target clamps probes	`[10, 1, 2, 0.993262]`	`[11, 1, 2, 0.989385]`	Failed
tight target	`[3853, 13, 482, 0.0001]`	`[3854, 13, 482, 0.0001]`	Failed
odd bit count	`[236, 4, 30, 0.050842]`	`[237, 4, 30, 0.050232]`	Failed
medium set	`[138, 6, 18, 0.020341]`	`[139, 6, 18, 0.019754]`	Failed
rejects p equal one	`invalid`	`invalid`	Passed
rejects empty set	`invalid`	`invalid`	Passed
another sizing	`[3402, 3, 426, 0.123012]`	`[3403, 3, 426, 0.122936]`	Failed
fractional ceil	`[55, 4, 7, 0.071319]`	`[56, 4, 7, 0.067896]`	Failed

SHA-256 / db27f4d6cc06b5c570cdecca285fe5a019d84b5c94ec34a8352b0cb25b6b9f54

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 = round(-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 fixture	Actual	Expected	Outcome
thousand items one percent	`[9652, 7, 1207, 0.01004]`	`[9653, 7, 1207, 0.010035]`	Failed
small set loose target	`[10, 2, 2, 0.303239]`	`[11, 2, 2, 0.267056]`	Failed
near-one target clamps probes	`[11, 1, 2, 0.989385]`	`[11, 1, 2, 0.989385]`	Passed
tight target	`[3853, 13, 482, 0.0001]`	`[3854, 13, 482, 0.0001]`	Failed
odd bit count	`[237, 4, 30, 0.050232]`	`[237, 4, 30, 0.050232]`	Passed
medium set	`[138, 6, 18, 0.020341]`	`[139, 6, 18, 0.019754]`	Failed
rejects p equal one	`invalid`	`invalid`	Passed
rejects empty set	`invalid`	`invalid`	Passed
another sizing	`[3402, 3, 426, 0.123012]`	`[3403, 3, 426, 0.122936]`	Failed
fractional ceil	`[55, 4, 7, 0.071319]`	`[56, 4, 7, 0.067896]`	Failed

SHA-256 / 3ee16825d0d30a0d9339850ba67c4c4b54529702a178ac2a319f3ada2840b483

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 fixture	Actual	Expected	Outcome
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 one	`invalid`	`invalid`	Passed
rejects empty set	`invalid`	`invalid`	Passed
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.256815+00:00.

Case digest / 027565a12390338ccff72ddf8f3376a14549e2f5c20c4e9d65b7d8694a4a8368