ExampleConstruction: AI-generatedVerification: AI-generatedPipeline-generatedprecheck pass

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

Huffman tree for a dyadic three-symbol source

Facts & Assumptions

Given: The source $p = (1 / 2, 1 / 4, 1 / 4)$ on symbols $1, 2, 3$ and the deterministic Huffman procedure.

[F1]

Deterministic binary Huffman coding: Equal weights are ordered by increasing serial number; the first selected node is the left child and the second is the right child.

[F2]

Finite binary source codes, extension, and expected length: $L_{p} (C) = \sum_{i} p_{i} ℓ_{i}$ .

[F3]

Base-two entropy of a finite source: $H_{2} (p) = - \sum_{i} p_{i} \log_{2} p_{i}$ .

[F4]

Huffman expected length is within one bit of entropy: If $m \geq 2$ , then $H_{2} (p) \leq L_{p} (C_{H}) < H_{2} (p) + 1$ .

[F5]

The deterministic Huffman code is prefix-optimal: The deterministic Huffman procedure returns a binary prefix code minimizing $L_{p} (C)$ among all binary prefix codes on the same alphabet.

[F6]

Information units and logarithm-base convention: $\log_{2} x = \ln x / \ln 2$ .

[F7]

Change of base and inversion of the positive-base real exponential: $\log_{2} (2^{u}) = u$ for every real $u$ .

Example

The weights of symbols 2 and 3 are tied for least, so the first merge combines them. The final tie is between symbol 1 and the merged node; the serial rule puts symbol 1 on the left. The code tree uses edge labels 0 on the left and 1 on the right; each leaf label is a source symbol, and reading its root path gives its codeword.

The diagram records the tree structure and edge convention; the verification below computes the codewords and lengths directly.

Verification

1.1F1givenconstruct

The first merge combines 2 and 3 into a node of weight $1 / 2$ . The active nodes are then $(1, 1 / 2)$ and the merged node of weight $1 / 2$ ; the serial tie-break puts 1 on the left and the merged node on the right. Thus $C_{H} (1) = 0$ , $C_{H} (2) = 10$ , and $C_{H} (3) = 11$ .

2.1F2F3F4F5F6F7step 1.1algebra∎

These lengths are $(1, 2, 2)$ , so [F2] gives $L_{p} (C_{H}) = \frac{1}{2} + \frac{1}{2} + \frac{1}{2} = \frac{3}{2}$ . By [F6] and [F7], $\log_{2} (1 / 2) = - 1$ and $\log_{2} (1 / 4) = - 2$ , so [F3] gives $H_{2} (p) = \frac{1}{2} + \frac{1}{2} + \frac{1}{2} = \frac{3}{2}$ as well, which satisfies the two-sided bound [F4]; [F5] confirms the optimal prefix-code conclusion.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

19 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Stanford EE376A, Information Theory Course Notes, Chapter 4: Lossless Compression (standard reference, not scraped)