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

priorkH bitsboundHuffmanmax
8 ke, uniform23.00003.00003.00003
8 ke, tent 1234 432122.84642.84642.90004
8 ke, tent, 3-way32.84641.79591.90003
120 fen, uniform26.90696.90696.93337
120 fen, uniform36.90694.35784.49175
120 fen, uniform126.90691.92661.98332
double-hour x fen1210.49192.92662.98193
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