What does Bloom Filters and HyperLogLog for Many Sites conclude, in numbers, about “HyperLogLog: the First 1-Bit, the Harmonic Mean and 1.04/√m”?
Answer: Chapter 2 opens HyperLogLog, recomputes the limiting constant 1.03896, and shows that the constant is 1.106 at m = 16 and that the abstract's example of 1.5 kilobytes corresponds to a standard error of 0.0230.
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.03896, 1.106, 16
| beta_inf = sqrt(3 ln 2 - 1) | 1.03896 |
| alpha_inf | 1 / (2 ln 2) = 0.72135 |
| m bias emp.SE SE*sqrt(m) paper in1s in2s in3s | |
| 16 -0.0030 | 0.2814 1.126 1.106 0.684 0.952 0.987 |
| 64 -0.0014 | 0.1304 1.043 1.054 0.686 0.955 0.994 |
| 256 -0.0002 | 0.0658 1.053 1.04 0.674 0.952 0.998 |
| 1024 -0.0002 | 0.0323 1.034 1.04 0.686 0.958 0.997 |
| 4096 -0.0001 | 0.0165 1.059 1.04 0.666 0.954 0.997 |
| paper: within 1, 2, 3 sigma in about 0.65, 0.95, 0.99 of cases |
Show the full program
# Chapter 2. p22: the 1.04 / sqrt(m) law checked by 4,000 sketches per m.
# Poisson model (as in the analysis of Flajolet et al. 2007): with an
# ideal hash and Poisson(n) distinct items, the items of one register
# are Poisson(lam = n / m) and P(register <= r) = exp(-lam * 2^-r), so a
# register is drawn exactly by inverting that law. n = 1,000,000; the
# Poisson spread of n itself adds a relative 0.001, negligible here.
# Raw estimator E = alpha_m m^2 / sum 2^-M_j (no range correction is
# needed at n >> m). Paper constants: beta_16 = 1.106, beta_32 = 1.070,
# beta_64 = 1.054, beta_128 = 1.046, beta_inf = sqrt(3 ln 2 - 1);
# alpha_inf = 1 / (2 ln 2).
import math
import random
rng = random.Random(20261113)
N, T = 1000000, 4000
BETA = {16: 1.106, 64: 1.054}
def alpha(m):
table = {16: 0.673, 32: 0.697, 64: 0.709}
return table.get(m, 0.7213 / (1.0 + 1.079 / m))
def draw(lam):
u = rng.random()
while u == 0.0:
u = rng.random()
x = lam / -math.log(u)
return 0 if x <= 1.0 else math.ceil(math.log2(x))
def sketch_estimate(m):
lam = N / m
regs = [draw(lam) for _ in range(m)]
return alpha(m) * m * m / math.fsum(2.0 ** -r for r in regs)
print("beta_inf = sqrt(3 ln 2 - 1) = %.5f" % math.sqrt(3 * math.log(2) - 1))
print("alpha_inf = 1 / (2 ln 2) = %.5f" % (0.5 / math.log(2)))
print(" m bias emp.SE SE*sqrt(m) paper in1s in2s in3s")
for m in (16, 64, 256, 1024, 4096):
rel = [sketch_estimate(m) / N - 1.0 for _ in range(T)]
mu = math.fsum(rel) / T
sd = math.sqrt(math.fsum((r - mu) ** 2 for r in rel) / (T - 1))
s = 1.04 / math.sqrt(m)
cover = [len([r for r in rel if abs(r) <= k * s]) / T
for k in (1, 2, 3)]
paper = "%.3f" % BETA[m] if m in BETA else " 1.04"
print("%4d %7.4f %8.4f %11.3f %6s %5.3f %5.3f %5.3f"
% (m, mu, sd, sd * math.sqrt(m), paper,
cover[0], cover[1], cover[2]))
print("paper: within 1, 2, 3 sigma in about 0.65, 0.95, 0.99 of cases")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 2: HyperLogLog: the First 1-Bit, the Harmonic Mean and 1.04/√m. 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 3 · Corrections at Both Ends: Linear Counting, Switch-Point Bias and Hash Width
- 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