What does Bloom Filters and HyperLogLog for Many Sites conclude, in numbers, about “The Bloom Filter: the False-Positive Formula, the Optimal Probe Count and 1.44 Times the Space”?
Answer: Chapter 4 measures Bloom filters and explains the optimal probe count and the space factor of 1.443.
Scope of the numbers: In an illustrative network, per-site unique visitors add up to 2.224 times the true number of people. Marked boxes separate published evidence, Python calculations (20 programs), classical sources and the author's hypotheses.
Data table
The numbers below are printed verbatim by the chapter's Python program and can be reproduced by running it. standard-library Python onlyprinted values that match the answer: 1.443
| base 2^-ln2 | 0.6185, factor 1/ln2 = 1.4427 |
| bits/key k*=c ln2 best int k FP at best k bits set at k | |
| 4.0 | 2.773 3 0.146892 0.528 |
| 6.0 | 4.159 4 0.056057 0.487 |
| 8.0 | 5.545 6 0.021577 0.528 |
| 9.6 | 6.654 7 0.009965 0.518 |
| 10.0 | 6.931 7 0.008194 0.503 |
| 12.0 | 8.318 8 0.003142 0.487 |
| 14.4 | 9.981 10 0.000989 0.501 |
| 16.0 | 11.090 11 0.000459 0.497 |
| 20.0 | 13.863 14 0.000067 0.503 |
| target FP bits/key Bloom floor log2(1/p) overhead | |
| 0.0500 | 6.24 4.32 1.443 |
| 0.0100 | 9.59 6.64 1.443 |
| 0.0010 | 14.38 9.97 1.443 |
| 0.0001 | 19.17 13.29 1.443 |
| cost of k | 1 at 10 bits/key: FP 0.0952 vs 0.0082 |
| cost of k | 14 at 10 bits/key: FP 0.0190 |
Show the full program
# Chapter 4. p42: the optimal number of hash probes and the 1.44 factor.
# Closed form p(k) = (1 - exp(-k / c))^k with c = m / n bits per key.
# Calculus gives k* = c ln 2, where half the bits are set and
# p = 2^-k* = 0.6185^c. For a target p the bits per key are
# c = log2(1/p) / ln 2 = 1.4427 log2(1/p), against the lower bound of
# log2(1/p) bits per key for any structure with no false negatives
# (Broder and Mitzenmacher 2004, sec. 2.2). Integer k found by scanning.
import math
LN2 = math.log(2)
def p_of(k, c):
return (1.0 - math.exp(-k / c)) ** k
print("base 2^-ln2 = %.4f, factor 1/ln2 = %.4f" % (0.5 ** LN2, 1 / LN2))
print("bits/key k*=c ln2 best int k FP at best k bits set at k")
for c in (4, 6, 8, 9.6, 10, 12, 14.4, 16, 20):
kbest = min(range(1, 40), key=lambda k: p_of(k, c))
print("%8.1f %9.3f %11d %13.6f %14.3f"
% (c, c * LN2, kbest, p_of(kbest, c),
1.0 - math.exp(-kbest / c)))
print("target FP bits/key Bloom floor log2(1/p) overhead")
for p in (0.05, 0.01, 0.001, 0.0001):
floor = math.log2(1.0 / p)
print("%9.4f %16.2f %16.2f %9.3f"
% (p, floor / LN2, floor, 1 / LN2))
print("cost of k = 1 at 10 bits/key: FP %.4f vs %.4f"
% (p_of(1, 10), p_of(7, 10)))
print("cost of k = 14 at 10 bits/key: FP %.4f" % p_of(14, 10))Single source and citation
Fan, Y. (2026). Bloom Filters and HyperLogLog Cardinality Estimation: Counting Unique Visitors and Deduplicating Orders across a Hundred Sites in Kilobytes (Version 1.0.0), Chapter 4: The Bloom Filter: the False-Positive Formula, the Optimal Probe Count and 1.44 Times the Space. 5D Library. DOI pending
DOI pending · monograph page goes live after publication · 5DL-B-294 · v1.0.0 · CC-BY-NC-ND-4.0
BibTeX
@book{fan2026294,
author = {Fan, Yafu},
title = {Bloom Filters and HyperLogLog Cardinality Estimation: Counting Unique Visitors and Deduplicating Orders across a Hundred Sites in Kilobytes},
year = {2026},
publisher = {5D Library},
edition = {1.0.0},
note = {DOI pending}
}Other chapter answers in this book
- Chapter 1 · The Memory Bill of Exact Deduplication: Why Unique Visitors Do Not Add Up
- Chapter 2 · HyperLogLog: the First 1-Bit, the Harmonic Mean and 1.04/√m
- Chapter 3 · Corrections at Both Ends: Linear Counting, Switch-Point Bias and Hash Width
- Chapter 5 · Order Deduplication: Filters Route but Never Reject, Windows Rotate by Generation, Counters Delete
- Chapter 6 · Merging a Hundred Sites, the Intersection Trap and the Privacy of Registers
- Chapter 7 · Classical Sources East and West: the Registration Rule of the Minor Minister and Laplace's Ratio of Births
- Chapter 8 · Closing the Loop: Registers-Only Weekly Reports for Tollbooth and Direct-Answer Pages, and a Pre-Registered Audit