DefinitionDefinition: Literature-sourcedProof: Not applicablePipeline-generated

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.

Base-two entropy of a finite source

Definition

For a finite source $p$ of Finite discrete sources and product blocks, define its base-two Shannon entropy, measured in bits, by $H_{2} (p) : = \frac{H (p)}{\ln 2} = - \sum_{i = 1}^{m} p_{i} \log_{2} p_{i} .$ Here $H (p) = - \sum_{i} p_{i} \ln p_{i}$ is the finite Shannon entropy in natural units from Finite distributions, entropy, divergence, and stochastic matrices. By Information units and logarithm-base convention, information quantities use natural logarithms by default and $\log_{2} t = \ln (t) / \ln 2$ . Substituting this identity termwise and using $\sum_{i} p_{i} = 1$ gives the displayed equality. Every $p_{i}$ is positive by the source convention, so no zero-term convention is needed here.

Depends on

Used by

Huffman expected length is within one bit of entropy Corollary
Ideal-real arithmetic coding is within two bits per block Corollary
The finite-register rational coder is within two bits per block Corollary
Huffman tree for a dyadic three-symbol source Example
Shannon bounds for finite binary codes Theorem

Dependency tree · two levels

7 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)
MIT OpenCourseWare 6.450, Memory-less sources, prefix free codes, and entropy (standard reference, not scraped)