What does Bloom Filters and HyperLogLog for Many Sites conclude, in numbers, about “Corrections at Both Ends: Linear Counting, Switch-Point Bias and Hash Width”?
Answer: Chapter 3 handles both ends: below 2.5 times the register count linear counting takes over, with a positive bias of 0.0144 at the switch point, and a 32-bit hash loses 0.1079 of a billion visitors.
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: 0.1079, 32
| threshold 2^32 / 30 | 143165577 |
| distinct n | 32-bit seen undercount 64-bit undercount |
| 1e+06 | 999884 0.0001 2.71e-14 |
| 1e+07 | 9988367 0.0012 2.71e-13 |
| 1e+08 | 98844829 0.0116 2.71e-12 |
| 1.432e+08 | 140839071 0.0165 3.88e-12 |
| 5e+08 | 471993428 0.0560 1.36e-11 |
| 1e+09 | 892117359 0.1079 2.71e-11 |
| 2e+09 | 1598931006 0.2005 5.42e-11 |
| 4e+09 | 2602611761 0.3493 1.08e-10 |
| n | 1e+09: corrected 1000000000, error amplified by 1.262 |
| n | 4e+09: corrected 4000000000, error amplified by 2.538 |
| hash 32 bits, b | 12: max register 21, needs 5 bits |
| hash 64 bits, b | 12: max register 53, needs 6 bits |
| hash 64 bits, b | 14: max register 51, needs 6 bits |
Show the full program
# Chapter 3. p32: a 32-bit hash runs out of room; a 64-bit hash does not.
# With an L-bit hash, n distinct items occupy about 2^L (1 - exp(-n/2^L))
# distinct hash values (balls in bins), so even a perfect sketch of the
# hash values undercounts. Flajolet et al. (2007) invert this above
# 2^32 / 30; the inversion is exact in expectation but multiplies any
# relative error in E by exp(n / 2^L), the slope of the inverse.
# Register width: values run up to L + 1 - b, so 5 bits for L = 32 and
# 6 bits for L = 64. Item counts below are illustrative.
import math
def occupied(n, bits):
return 2.0 ** bits * -math.expm1(-n / 2.0 ** bits)
def corrected(e, bits):
return -(2.0 ** bits) * math.log1p(-e / 2.0 ** bits)
print("threshold 2^32 / 30 = %.0f" % (2.0 ** 32 / 30))
print(" distinct n 32-bit seen undercount 64-bit undercount")
for n in (1e6, 1e7, 1e8, 1.432e8, 5e8, 1e9, 2e9, 4e9):
s32 = occupied(n, 32)
s64 = occupied(n, 64)
print("%12.4g %13.0f %11.4f %18.2e"
% (n, s32, 1.0 - s32 / n, 1.0 - s64 / n))
for n in (1e9, 4e9):
print("n = %.0e: corrected %.0f, error amplified by %.3f"
% (n, corrected(occupied(n, 32), 32), math.exp(n / 2.0 ** 32)))
for bits, b in ((32, 12), (64, 12), (64, 14)):
top = bits + 1 - b
print("hash %d bits, b = %d: max register %d, needs %d bits"
% (bits, b, top, top.bit_length()))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 3: Corrections at Both Ends: Linear Counting, Switch-Point Bias and Hash Width. 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 4 · The Bloom Filter: the False-Positive Formula, the Optimal Probe Count and 1.44 Times the Space
- 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