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_inf1 / (2 ln 2) = 0.72135
m bias emp.SE SE*sqrt(m) paper in1s in2s in3s
16 -0.00300.2814 1.126 1.106 0.684 0.952 0.987
64 -0.00140.1304 1.043 1.054 0.686 0.955 0.994
256 -0.00020.0658 1.053 1.04 0.674 0.952 0.998
1024 -0.00020.0323 1.034 1.04 0.686 0.958 0.997
4096 -0.00010.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