What does The Bit Budget of Tieban Shenshu conclude, in numbers, about “The Kaoke Decision Tree: Entropy Bounds on the Mean Number of Questions and Huffman Optimality”?
Answer: Chapter 2 writes kaoke as a decision tree: twelve-way questions fix one of 120 fen in 1.9833 questions on average with a Huffman tree.
Scope of the numbers: Its parameters are illustrative; all calculations are generated by its programs; it analyses structure and probability, makes no reading of any individual, and is not legal or financial advice. Chapter 5 shows that a verse carries at most 0.5307 bits of expected information and that at an illustrative scale 19.01 people are born each minute.
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.9833, 120
| prior | k | H bits | bound | Huffman | max |
|---|---|---|---|---|---|
| 8 ke, uniform | 2 | 3.0000 | 3.0000 | 3.0000 | 3 |
| 8 ke, tent 1234 4321 | 2 | 2.8464 | 2.8464 | 2.9000 | 4 |
| 8 ke, tent, 3-way | 3 | 2.8464 | 1.7959 | 1.9000 | 3 |
| 120 fen, uniform | 2 | 6.9069 | 6.9069 | 6.9333 | 7 |
| 120 fen, uniform | 3 | 6.9069 | 4.3578 | 4.4917 | 5 |
| 120 fen, uniform | 12 | 6.9069 | 1.9266 | 1.9833 | 2 |
| double-hour x fen | 12 | 10.4919 | 2.9266 | 2.9819 | 3 |
Show the full program
# Chapter 2. p21: Ke-checking as a decision tree. For a target with
# prior p, any tree of k-way questions needs on average at least
# H(p) / log2 k questions (Shannon), and Huffman's construction reaches
# the best average (within one question of the bound). Priors are
# illustrative: uniform over 8 ke or 120 fen, and a "tent" prior over 8
# ke (weights 1 2 3 4 4 3 2 1) for a client who says "about the middle
# of the double-hour".
import heapq
import math
def entropy(p):
return -math.fsum(x * math.log2(x) for x in p if x > 0)
def huffman_depths(p, k):
# k-ary Huffman; pad with zero-weight leaves so (n - 1) % (k - 1) == 0
n = len(p)
pad = 0
while (n + pad - 1) % (k - 1):
pad += 1
heap = [(w, i, (i,)) for i, w in enumerate(list(p) + [0.0] * pad)]
heapq.heapify(heap)
depth = [0] * (n + pad)
tick = n + pad
while len(heap) > 1:
group = [heapq.heappop(heap) for _ in range(k)]
leaves = ()
for _, _, lv in group:
for j in lv:
depth[j] += 1
leaves += lv
w = math.fsum(g[0] for g in group)
heapq.heappush(heap, (w, tick, leaves))
tick += 1
return depth[:n]
def report(name, w, k):
tot = math.fsum(w)
p = [x / tot for x in w]
h = entropy(p)
d = huffman_depths(p, k)
avg = math.fsum(pi * di for pi, di in zip(p, d))
print(" {:<22}{:>3} {:7.4f} {:7.4f} {:7.4f} {:>3}".format(
name, k, h, h / math.log2(k), avg, max(d)))
print(" prior k H bits bound Huffman max")
report("8 ke, uniform", [1] * 8, 2)
report("8 ke, tent 1234 4321", [1, 2, 3, 4, 4, 3, 2, 1], 2)
report("8 ke, tent, 3-way", [1, 2, 3, 4, 4, 3, 2, 1], 3)
report("120 fen, uniform", [1] * 120, 2)
report("120 fen, uniform", [1] * 120, 3)
report("120 fen, uniform", [1] * 120, 12)
report("double-hour x fen", [1] * 1440, 12)Single source and citation
Fan, Y. (2026). Tieban Shenshu Ke-Fen Decision Trees, Affine Coding of the Verse Bank and Entropy Lower Bounds on Elicitation (Version 1.0.0), Chapter 2: The Kaoke Decision Tree: Entropy Bounds on the Mean Number of Questions and Huffman Optimality. 5D Library. DOI pending
DOI pending · monograph page goes live after publication · 5DL-B-157 · v1.0.0 · CC-BY-NC-ND-4.0
BibTeX
@book{fan2026157,
author = {Fan, Yafu},
title = {Tieban Shenshu Ke-Fen Decision Trees, Affine Coding of the Verse Bank and Entropy Lower Bounds on Elicitation},
year = {2026},
publisher = {5D Library},
edition = {1.0.0},
note = {DOI pending}
}Other chapter answers in this book
- Chapter 1 · The Bit Budget of a Verse Bank: What the Double-Hour, the Ke, the Fen and the Bank Are Worth
- Chapter 3 · An Affine Cipher for Verse Numbers: Invertibility, Key Space and Known-Pair Attacks
- Chapter 4 · Questions Are Leaks: The Cold Reader's Entropy Budget and Why a Match Is Nearly Certain
- Chapter 5 · Verse Specificity and Clock Resolution: Barnum Statements, Same-Minute Births and Twins
- Chapter 6 · Noisy Answers: The Liar Game, Year-Boundary Errors in Birth Animals, and Fano's Inequality
- Chapter 7 · The Classical Sources: The Combinatorics of the Sound-and-Tone Chart and Leibniz's Binary
- Chapter 8 · Practice and Refutation: A Bit Budget for Intake, Red Lines for Scripts, and a Pre-Registered Test