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
| delta | D(p||q) | H+D | Shannon L | in bound | Huffman(q) | excess |
|---|---|---|---|---|---|---|
| 0.00 | 0.000 | 6.372 | 6.824 | yes | 6.406 | 0.000 |
| 0.25 | 0.040 | 6.412 | 6.880 | yes | 6.430 | 0.025 |
| 0.50 | 0.136 | 6.508 | 6.972 | yes | 6.517 | 0.112 |
| 1.00 | 0.758 | 7.130 | 7.614 | yes | 7.083 | 0.678 |
| 2.00 | 2.016 | 8.388 | 8.932 | yes | 8.295 | 1.889 |
| 4.00 | 2.876 | 9.248 | 9.724 | yes | 9.061 | 2.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
- Chapter 1 · The Linear Bill: Context Cost of Loading Everything and the Entropy Bound
- Chapter 2 · Building Huffman Trees: Many-Way Merging, Dummy Leaves and the Price of a Menu
- Chapter 3 · Navigable Trees: the Price of Alphabetic Order and the Accumulation of Wrong Turns
- Chapter 4 · The Branching Factor: Depth against Width, and Hanging Popular Tools on the Root
- Chapter 5 · Queueing with Cold Starts: the Delay Bill of Lazy Loading and How Long to Stay Warm
- Chapter 7 · Classical Sources East and West: Offices and Duties in the Rites of Zhou and Dewey's Decimal Scheme
- Chapter 8 · Closing the Loop: a Monthly Report on Catalogue Layering and Call Frequency