What does Lazy Tool Hubs conclude, in numbers, about “Frequency Drift: the Cost of Wrong Frequencies and When to Rebuild the Routing Tree”?

Answer: The cost of using wrong frequencies is roughly the relative entropy: small drift is almost harmless, drift 1.0 adds 0.678 decisions per lookup, and large drift makes a frequency tree worse than a balanced one. The trigger for rebuilding must not be the in-sample gap, which fires every month; it should be a held-out test, so that rebuilding happens only when frequencies really change. With this, the mathematics of routing trees is complete. The next chapter leaves the computer for a while and goes back to an administrative order more than two thousand years old and a library scheme from a century and a half ago, to see how earlier ages layered hundreds of offices and thousands of books, what they got right and what they missed.

Scope of the numbers: Selection accuracy lacks reliable peer-reviewed primary evidence and is demoted to an author's hypothesis. Marked boxes separate published evidence, runnable Python calculations (17 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.678

deltaD(p||q)H+DShannon Lin boundHuffman(q)excess
0.000.0006.3726.824yes6.4060.000
0.250.0406.4126.880yes6.4300.025
0.500.1366.5086.972yes6.5170.112
1.000.7587.1307.614yes7.0830.678
2.002.0168.3888.932yes8.2951.889
4.002.8769.2489.724yes9.0612.656
H(p) = 6.372 bits, Huffman on p = 6.406 decisions
Show the full program
# Chapter 6. p61: a tree built for last month's shares costs H + D.
# True shares p: Zipf(1) over N = 300 tools. Stale shares q: the same
# Zipf weights over a ranking perturbed by noise of size delta (seeded,
# illustrative). With code lengths ceil(-log2 q) the expected path is
# bounded by H(p) + D(p||q) <= L < H(p) + D(p||q) + 1 (the wrong-code
# theorem in Cover and Thomas). The Huffman tree built on q is shown
# too, with its excess over the Huffman tree built on the true p.
import heapq
import math
import random

rng = random.Random(20261113)
N = 300


def zipf(n, a):
    w = [1.0 / (i ** a) for i in range(1, n + 1)]
    t = math.fsum(w)
    return [x / t for x in w]


def depths(p):
    items = [(x, i, (i,)) for i, x in enumerate(p)]
    heapq.heapify(items)
    seq, depth = len(p), [0] * len(p)
    while len(items) > 1:
        a, b = heapq.heappop(items), heapq.heappop(items)
        for i in a[2] + b[2]:
            depth[i] += 1
        heapq.heappush(items, (a[0] + b[0], seq, a[2] + b[2]))
        seq += 1
    return depth


p = zipf(N, 1.0)
h = -math.fsum(x * math.log2(x) for x in p)
opt = math.fsum(x * d for x, d in zip(p, depths(p)))
w = zipf(N, 1.0)
noise = [rng.gauss(0.0, 1.0) for _ in range(N)]
print("delta  D(p||q)   H+D    Shannon L  in bound  Huffman(q)  excess")
for delta in (0.0, 0.25, 0.5, 1.0, 2.0, 4.0):
    score = [math.log(i + 1) + delta * noise[i] for i in range(N)]
    order = sorted(range(N), key=lambda i: (score[i], i))
    q = [0.0] * N
    for r, i in enumerate(order):
        q[i] = w[r]
    d = math.fsum(x * math.log2(x / y) for x, y in zip(p, q))
    ls = math.fsum(x * math.ceil(-math.log2(y)) for x, y in zip(p, q))
    lh = math.fsum(x * dd for x, dd in zip(p, depths(q)))
    ok = h + d <= ls < h + d + 1
    print("%5.2f %8.3f %7.3f %10.3f %8s %11.3f %7.3f"
          % (delta, d, h + d, ls, "yes" if ok else "NO", lh, lh - opt))
print("H(p) = %.3f bits, Huffman on p = %.3f decisions" % (h, opt))

Single source and citation

Fan, Y. (2026). A Lazy-Loading Private Tool Hub: Near-Zero Opening Context for Hundreds of Checkers and On-Demand Routing Trees (Version 1.0.0), Chapter 6: Frequency Drift: the Cost of Wrong Frequencies and When to Rebuild the Routing Tree. 5D Library. DOI pending

DOI pending · monograph page goes live after publication · 5DL-B-257 · v1.0.0 · CC-BY-NC-ND-4.0

BibTeX
@book{fan2026257,
  author    = {Fan, Yafu},
  title     = {A Lazy-Loading Private Tool Hub: Near-Zero Opening Context for Hundreds of Checkers and On-Demand Routing Trees},
  year      = {2026},
  publisher = {5D Library},
  edition   = {1.0.0},
  note      = {DOI pending}
}

Other chapter answers in this book