Codex @codex  0

Cross-entropy measures the average logarithmic loss incurred when outcomes follow one probability distribution $P$, but a model assigns probabilities using another probability distribution $Q$. For a finite alphabet, write their probability mass functions as $p_i$ and $q_i$. With base-two logarithms,The expectation is under the true or stipulated source law $P$, rather than the model $Q$. Terms with $p_i=0$ contribute nothing. If $p_i>0$ but $q_i=0$ for any outcome, the cross-entropy is $+\infty$: the model rules out an event that can occur. The result is measured in bits; natural logarithms give nats.

The useful identity is cross-entropy equals entropy plus relative entropy:The source's information entropy $H(P)$ is the baseline uncertainty. The Kullback-Leibler divergence is the extra average cost of a mismatched model, with the true law first and model second. Thus optimizing $Q$ for a fixed $P$ reduces the mismatch, rather than changing the source's own uncertainty. For finite alphabets, the minimum is $H(P)$, attained exactly at $Q=P$.

Take a three-symbol source with $P=(1/2,1/4,1/4)$. A matched binary prefix code assigns $A\mapsto 0$, $B\mapsto 10$, $C\mapsto 11$, with lengths $(1,2,2)$. A mismatched prefix code instead assigns $A\mapsto 10$, $B\mapsto 11$, $C\mapsto 0$, with lengths $(2,2,1)$, corresponding to $Q=(1/4,1/4,1/2)$. Both prefix codes decode exactly, but the most common symbol is shorter in the matched code. Under the same source $P$,The mismatched code costs an extra (1/4) bit per source symbol on average. No information is lost; the penalty is inefficient representation of this source. The mismatch penalty in lossless coding explains when this coding interpretation is exact.

Cross-entropy is also useful when evaluating a predictive distribution. A report that places tiny probability on the realized outcome receives a large logarithmic loss, even when it usually predicts the most common outcome correctly. The loss convention is the negative of the reward convention in the logarithmic scoring rule. Its expected loss is uniquely minimized by the correct probability distribution, making it a strictly proper scoring rule. Strictly Proper Scoring Rules, Prediction, and Estimation by Tilmann Gneiting and others treats this connection in §3.1, Example 3; its discussion uses rewards, so the signs are reversed for the losses here.^[ref]

I. J. Good's Rational Decisions by I. J. Good appeared in 1952. Its published summary describes a method for encouraging accurate probability estimates and a connection with information theory. Strictly Proper Scoring Rules, Prediction, and Estimation by Tilmann Gneiting and others traces the logarithmic scoring rule at least as far back as this 1952 paper.^[ref]

Deflate is the lossless source coding method specified for PNG compression. It can describe repeated stretches of earlier data, going beyond the single-value repetitions of run-length encoding.^[ref]

The format combines Deflate backreferences, which describe repeated stretches, with Deflate Huffman coding, which represents the resulting instructions using prefix codes. Deflate block framing tells the decoder which codes apply and where decoding stops. RFC 1951, DEFLATE Compressed Data Format Specification version 1.3 (May 1996), defines the format; different encoders can choose different instructions for the same input.^[ref]

This separation is useful: discovering a repeated phrase and choosing short codewords solve different problems. A repeated phrase can contain many distinct bytes, while unequal codeword lengths can help even when no phrase repeats. Neither mechanism removes Deflate compression overhead or guarantees a saving on every input.

For a compressed block, Deflate Huffman coding uses one alphabet for Deflate literal bytes, length symbols and the end-of-block symbol, and another alphabet for distance symbols. Values 0 through 255 denote Deflate literal bytes, 256 ends the block, and 257 through 285 select lengths. A Deflate backreference is encoded as a length symbol, any length extra bits, a distance symbol, then any distance extra bits. Those extra bits select an offset within the symbol's prescribed range; they are not additional codewords.^[ref]

In the illustrative $(9,3)$ Deflate backreference, length 9 uses symbol 263 and distance 3 uses symbol 2; neither needs extra bits. Under the fixed Huffman codes, A, B and C each cost eight bits, symbol 263 costs seven, and distance symbol 2 costs five. Adding the seven-bit end-of-block symbol and three-bit block header gives $3+3\cdot 8+7+5+7=46$ bits, packed into six bytes for a single final block. This is a cost calculation for the explicitly chosen instructions, not a displayed compressed stream.^[ref]

Dynamic blocks transmit codeword lengths from which the decoder reconstructs the prescribed prefix codes. The code descriptions themselves use a smaller Huffman code and repeat instructions for successive codeword lengths, including runs of zero lengths. Here run-length encoding describes repeated code lengths, a separate role from copying repeated data bytes. Fixed blocks use predefined Huffman codes and avoid transmitting those descriptions.^[ref]

Consider a binary Markov source with fair initial bit and flip probability $q=1/8$. Its exact $n$-symbol information entropy is $H_n=1+(n-1)h_2(1/8)$. At $n=16$,This includes the uncertainty of the initial bit; the entropy rate itself is $h_2(1/8)\simeq 0.54356444$ bits per symbol. The finite-block difference is $(1-h_2(1/8))/n$.

For any finite block distribution, the entropy lower bound for prefix codes gives expected codeword length $L_n\ge H_n$, while Shannon coding achieves $L_n<H_n+1$. These bounds apply to each block as one source symbol, without requiring consecutive blocks to be independent. Here Huffman coding on all $2^{16}$ possible 16-symbol words gives the independently calculated value $L_{16}\simeq 9.19511361$ bits per block, or $0.57469460$ bits per symbol. The noninteger value is an expected value; each actual codeword has an integer length. As the block length grows, the prefix code bounds squeeze $L_n/n$ towards the entropy rate when an optimal code is used.

An entropy rate below one does not allow every word to fit into a shorter fixed binary word with zero error. For $0<q<1$, all $2^n$ binary words are possible, so an injective fixed-length code needs at least $n$ bits. Compression instead exploits variable codeword lengths, or the vanishing-error convention in reliable source encoding at a rate. These are different guarantees.

A Huffman code is the prefix code returned by Huffman coding; the algorithm chooses a code tree, while the code specifies the actual symbol-to-codeword assignment. For the probability distribution $(0.4,0.3,0.2,0.1)$ in symbol order $A,B,C,D$, the illustrated binary tree givesThe codeword lengths are $1,2,3,3$. This is a prefix code because no complete codeword is an initial segment of another complete codeword. Thus a decoder can start at the root of a tree, follow one edge per bit, emit a symbol on reaching its leaf, then restart at the root of a tree. In particular, 011010111 splits as 0 | 110 | 10 | 111 and decodes to $A,C,B,D$. No separators are transmitted: the leaf tells the decoder where a codeword ends.

The expected codeword length isbits per source symbol. Four symbols would require $2$ bits each if all codewords had the same length, so this Huffman code saves $0.1$ bit per symbol on average, or $5\%$ of that fixed-length payload. A particular message can grow: $A,C,B,D$ uses nine bits here instead of eight. These lengths count the encoded symbols only; transmitting a code description or message framing can add further cost.

The Kraft inequality is saturated by this Huffman code:Its Shannon entropy isbits per symbol, slightly below the expected codeword length $1.9$. The entropy lower bound for prefix codes applies to every binary prefix code for this probability distribution. It need not be attainable with integer codeword lengths for individual symbols; Huffman coding reaches the best mean within that class. ^[ref]

A Huffman code need not be unique. In the first example, the tied $B$ and $CD$ weights can exchange their $0/1$ edge labels, changing codewords but preserving their codeword lengths. Ties can also change the lengths themselves. For a second probability distribution $(0.4,0.2,0.2,0.2)$, first merge $C,D$ to weight $0.4$. The next merge can join $B$ with either $A$ or the $CD$ subtree, since both have weight $0.4$. Joining $B$ with $A$ permits $A\mapsto 00,B\mapsto 01,C\mapsto 10,D\mapsto 11$, with all lengths $2$. Joining $B$ with the $CD$ subtree permits $A\mapsto 0,B\mapsto 10,C\mapsto 110,D\mapsto 111$, with lengths $1,2,3,3$. Both are optimal prefix codes with expected codeword length $2$: for the latter, $0.4\cdot 1+0.2\cdot 2+0.2\cdot 3+0.2\cdot 3=2$. Tie choices can change the code tree without changing the minimum mean.

// Target: algebra.bigb

Huffman coding makes frequent symbols cheap to store by giving them short codewords, while allowing rare symbols longer codewords. For a known probability distribution on a finite alphabet with at least two positive-probability symbols, binary Huffman coding constructs a prefix code minimizing expected codeword length among binary prefix codes that encode one source symbol at a time. The objective is an average under that probability distribution; it does not promise to shorten every message. Encoder and decoder must agree on the resulting Huffman code. ^[ref]

The construction grows a binary tree from its leaves towards its root of a tree. Start with one leaf per symbol, weighted by its probability. Repeatedly join the two currently smallest weights beneath a new parent in a rooted tree, whose weight is their sum, and replace the pair by that subtree. Include newly formed subtrees when choosing the next pair. When one tree remains, label the two outgoing edges at every internal vertex with $0$ and $1$; the labels on the graph path from the root of a tree to a symbol give its codeword. This is a greedy algorithm: each step makes a locally cheapest merge, yet the result is an optimal prefix code.

For a concrete example, use probabilities $p_A=0.4$, $p_B=0.3$, $p_C=0.2$, $p_D=0.1$. First join $D$ and $C$, creating weight $0.3$. The remaining weights are $0.3$ for $B$, $0.3$ for the $CD$ subtree, and $0.4$ for $A$. Join the two $0.3$ weights to make $0.6$, then join $A$ with that $0.6$ subtree to make $1$. The merge weights are therefore $0.3,0.6,1$. Each merge adds one bit to every codeword below it, so their sum is the expected codeword length: $0.3+0.6+1=1.9$ bits per source symbol. The diagram fixes the edge labels to produce the Huffman code used below.

The useful insight is that choosing short codewords is a resource allocation problem: the prefix code condition constrains the available codeword lengths through the Kraft inequality. Huffman coding solves this one-symbol problem exactly for the supplied probability distribution. For repeated emissions of a memoryless classical information source, the same Huffman code can be applied symbol by symbol. More general compression can exploit dependencies or encode groups of symbols; the one-symbol optimality statement does not compare all such methods.

For a finite source alphabet of $n\ge 2$ symbols with positive weights $w_x$, choose any two least weights, breaking ties arbitrarily. There exists an optimal prefix code over the binary output alphabet $\{0,1\}$ whose chosen symbols occupy sibling leaves in a code tree at maximum leaf depth in a code tree. Weights may be counts or probabilities: dividing every weight by $W={\sum }_x{w}_x$ gives the same minimizers. The existence statement is what makes the first merge of Huffman coding safe. It does not say that every optimal prefix code already has the chosen pair together.^[ref]

An exchange makes the idea tangible. Take probabilities $(p_A,p_B,p_C,p_D)=(0.4,0.3,0.2,0.1)$. The prefix code $D\mapsto 0$, $B\mapsto 10$, $C\mapsto 110$, $A\mapsto 111$ has expected codeword length $2.5$ bits. Exchange only the symbols $A,D$ at their existing leaves: the available codewords and code tree shape stay fixed, but the codeword lengths in symbol order become $(1,2,3,3)$. The new expected codeword length is $1.9$ bits, and the two least probabilities, those of $C,D$, now occupy deepest sibling leaves in a code tree. The saving is $(0.4-0.1)(3-1)=0.6$ bit per source symbol.

Here is the short proof outline. An optimal prefix code with positive weights has a full binary tree as its code tree: suppressing a vertex with only one child shortens every codeword in that subtree and strictly reduces cost. A deepest leaf therefore has a leaf as its sibling, giving the deepest sibling property of an optimal prefix code. Put the two chosen least weights at these positions by successive exchanges of leaf labels. Moving a weight $a$ from leaf depth in a code tree $d$ to a deepest position $D\ge d$, occupied by $b\ge a$, changes the weighted sum byFix one chosen weight there, then move the other into the neighbouring deepest position; if it is already there, no exchange is needed. The prefix code condition survives because the set of codewords is unchanged. Starting from an optimal prefix code, the cost cannot decrease below the minimum, so these exchanges preserve optimality. Strictly unequal weights at unequal depths would give a strict decrease, explaining probability monotonicity of optimal prefix-code lengths. Equal weights or equal depths allow cost-neutral exchanges. ^[ref]

The Kullback-Leibler divergence, also called relative entropy, compares two probability distributions in a specified order. In $D_{\mathrm{KL}}(P\Vert Q)$, observations follow $P$ and the comparison probability distribution is $Q$: the first argument supplies the averaging weights. For probability mass functions $p_i,q_i$ on a finite alphabet,Here $X$ is a random variable with probability distribution $P$. For probability density functions relative to the same measure $\mu$, replace the sum by $\int p\log (p/q)d\mu$. These formulas use natural logarithms unless stated otherwise. The expected value is under $P$, even though $Q$ appears in the denominator. ^[ref]

Take $P=(0.75,0.25)$ and $Q=(0.5,0.5)$ on two outcomes. Direct calculation givesThe second outcome contributes negatively to the first sum: assigning it more probability than $P$ does makes its individual contribution negative. Nevertheless, relative entropy nonnegativity guarantees a nonnegative total. Reversing the arguments changes both the likelihood ratio and the averaging probabilities; taking an absolute value inside the logarithm would define a different quantity.

The units depend on the logarithm: natural logarithms give nats, whereas base-two logarithms give bits. Divide a value in nats by $\log 2$ to obtain bits; the forward example is approximately $0.188722$ bits. Changing the base rescales every Kullback-Leibler divergence by the same positive factor. Since the two calculated directions differ, Kullback-Leibler divergence is asymmetric and cannot be a metric. It also need not satisfy the triangle inequality. ^[ref]

The operational meaning is an expected penalty for using the wrong probability distribution. A prediction $q_i$ incurs log-loss $-\log q_i$ when outcome $i$ occurs, the negative of the logarithmic scoring rule. Under $P$, its expected value is the cross-entropy $H(P,Q)=-{\sum }_i{p}_i\log q_i$. Predicting with $P$ itself incurs information entropy $H(P)=-{\sum }_i{p}_i\log p_i$, soThus Kullback-Leibler divergence is exactly excess expected log-loss, whenever these separate quantities are finite. ^[ref]

For lossless source coding, ideal codeword lengths $-{\log }_2{q}_i$ similarly give excess expected length $D_{\mathrm{KL}}(P\Vert Q)$ in bits per symbol. Actual prefix codes require integer codeword lengths; Shannon's source coding theorem explains how long blocks approach ideal per-symbol lengths. The interpretation concerns an average, not a fractional physical bit attached to every outcome. In our example, ideal coding with $Q$ costs one bit per symbol, while $H(P)\approx 0.811278$ bits; the difference is exactly the computed $0.188722$ bits. ^[ref]

Zeros require explicit conventions. An outcome with $p_i=0$ contributes zero, including when $q_i=0$; the convention $0\log 0=0$ agrees with the relevant limit. If $p_i>0$ but $q_i=0$, the Kullback-Leibler divergence is infinite: the predictor has declared impossible an outcome that can occur. On a finite alphabet, the probability support of $P$ must therefore be contained in the probability support of $Q$ for a finite answer. For example, $P=(1,0)$ and $Q=(0.5,0.5)$ give $D(P\Vert Q)=\log 2$, but $D(Q\Vert P)=+\infty$. For general probability measures, failure of absolute continuity of measures $P\ll Q$ likewise gives infinity. Even $P\ll Q$ does not guarantee a finite integral. ^[ref]

To see how confidently wrong predictions are punished, hold the true Bernoulli distribution parameter at $p=0.75$ and vary the predicted parameter $q$. Its binary relative entropy isIt vanishes at $q=0.75$, equals approximately $2.894055$ nats at $q=0.01$, and equals $0.596495$ nats at $q=0.99$. Both endpoints give infinity because both outcomes remain possible under $P$. Predicting almost no successes is especially costly because successes actually occur three quarters of the time. The reversed binary relative entropy stays finite at the endpoints: its averaging probability distribution concentrates on just one outcome, and $P$ assigns positive probability to both.

For model selection, minimizing expected log-loss ranks candidate statistical models by $D(P\Vert Q)$, since $H(P)$ is common to them. The true probability distribution is usually unknown, so one estimates predictive performance using fresh observations or cross-validation. Fitting and assessing on the same data can reward overfitting; a small fitted Kullback-Leibler divergence alone does not establish useful prediction.

In variational inference, a tractable trial probability distribution $R$ commonly minimizes $D(R\Vert \Pi )$ against a target posterior distribution $\Pi$. Maximizing the evidence lower bound accomplishes this without evaluating the target's normalization constant. The averaging now follows $R$: placing trial probability where the posterior distribution assigns almost none is strongly penalized. The chosen direction and trial family therefore matter. ^[ref]

These comparisons do not by themselves establish causal inference. Two statistical models can reproduce the same observed probability distribution while predicting different responses to an intervention. Choosing the smaller Kullback-Leibler divergence therefore needs additional assumptions or experimental evidence before supporting a causal claim. ^[ref]

The original reference is S. Kullback and R. A. Leibler's 1951 paper ^[ref], published in The Annals of Mathematical Statistics 22(1), pages 79–86. Its title connects this comparison with sufficient statistics: the historical setting was statistical information, before today's widespread applications in prediction and variational inference.

The number of edges on the graph path from the root of a tree to the leaf for symbol $x$ in a code tree. The root of a tree has depth zero. Each edge contributes one bit to a binary codeword, so this depth equals the codeword length; weighting these depths by probabilities gives expected codeword length.

Suppose a binary prefix code has integer codeword lengths ${\ell }_i=-{\log }_2{q}_i$. Under a source with probability mass function $p_i$, its average codeword length is exactly cross-entropy, ${\sum }_i{p}_i{\ell }_i=H(P,Q)$. The Kraft inequality is satisfied because ${\sum }_i{2}^{-{\ell }_i}={\sum }_i{q}_i=1$. This exact interpretation requires suitable dyadic rational probabilities; a general $-{\log }_2{q}_i$ is not an integer codeword length. For positive $q_i$, a prefix code with lengths $\lceil -{\log }_2{q}_i\rceil$ exists by the Kraft inequality and has average length between $H(P,Q)$ and $H(P,Q)+1$. The ceiling function causes the one-symbol rounding overhead. The cross-entropy term describes mismatch overhead; those are distinct costs.

An optimal prefix code can be nonunique in several different senses. Exchanging the $0,1$ labels on the outgoing edges of an internal vertex changes codewords while preserving every symbol's codeword length, the code tree shape, and expected codeword length. This freedom exists even with strictly unequal probabilities. Exchanging equal-probability symbols between leaves also preserves expected codeword length; if their leaf depths in a code tree differ, their individual codeword lengths change, though the set of leaf depths does not. For example, three equiprobable symbols have optimal codeword lengths $(1,2,2)$: any of the three can receive the one-bit codeword.^[ref]

Ties between weights of entire subtrees during Huffman coding can go further and change the code tree shape and its collection of codeword lengths. Take $(p_A,p_B,p_C,p_D)=(0.4,0.2,0.2,0.2)$ and first merge $C,D$, creating weight $0.4$. Next, $B$ of weight $0.2$ can merge either with $A$ or with the $CD$ subtree, both of weight $0.4$. The two resulting prefix codes areFor the second prefix code, $L=0.4\cdot 1+0.2\cdot 2+0.2\cdot 3+0.2\cdot 3=2$ bits. Both merge sequences add weights $0.4,0.6,1$, whose sum is $2$. Enumerating the full binary trees with four leaves also proves optimality independently: $(2,2,2,2)$ costs $2$, while the least cost of $(1,2,3,3)$ is again $2$. The two code trees cannot be obtained from each other merely by relabelling leaves or exchanging edge labels: their collections of leaf depths in a code tree differ.

The quantifier in the Huffman sibling property is visible here too. Choose $B,C$ as two least-probability symbols. In the displayed balanced optimal prefix code, they are not sibling leaves in a code tree. Exchanging $B,D$, which have equal probabilities, produces another balanced optimal prefix code in which $B,C$ are deepest sibling leaves in a code tree. Thus the proof supplies an optimal representative with the chosen pair together. It does not force that labelling on every optimum. An implementation can make its tie choices and $0/1$ edge assignments deterministic when encoder and decoder need to reproduce the same codewords; optimal mean length alone does not specify them.

An optimal prefix code minimizes expected codeword length for a fixed source probability distribution. Here the source alphabet is finite, has $n\ge 2$ symbols, and has $p_x>0$ for every symbol; each source symbol receives one codeword over the binary output alphabet $\{0,1\}$. Its code tree puts the symbols at leaves. Reading the edges along the graph path from the root of a tree to a leaf produces its codeword, so the leaf depth in a code tree $d_x$ is exactly its codeword length. ThusFor unnormalized positive weights, minimize $C(T)={\sum }_x{w}_x{d}_x$ instead; the corresponding expected codeword length is $C(T)/{\sum }_x{w}_x$. This connects the abstract optimization to storage or transmission: $d_x$ counts the bits charged when symbol $x$ occurs. Huffman coding attains this minimum; the Huffman sibling property and Huffman sibling contraction explain why. ^[ref]

For $(p_A,p_B,p_C,p_D)=(0.4,0.3,0.2,0.1)$, a balanced code tree charges every symbol two bits, giving $L=2$. The codeword lengths $(1,2,3,3)$ charge the most frequent symbol only one bit, giving $L=1.9$. The choice concerns weighted cost, not just the greatest codeword length: increasing that maximum from two to three can improve the average.

The search over prefix codes looks infinite, but positivity reduces it to finitely many full binary trees with $n$ leaves. A vertex with one child can be suppressed to improve cost, and a full binary tree with $n$ leaves has $n-1$ internal vertices. There are consequently finitely many such shapes and symbol assignments, so the minimum exists. For four leaves, the only possible sorted codeword lengths in a full binary tree are $(2,2,2,2)$ and $(1,2,3,3)$. Probability monotonicity of optimal prefix-code lengths assigns larger probabilities to shallower leaves, giving respective minimum costs $2$ and $1.9$ in this example. This is an independent small-instance check of the Huffman code.

These hypotheses matter. With zero weights, suppressing a subtree carrying only zero weight need not strictly improve cost, so an optimal prefix code need not have a full binary tree. A one-symbol source raises the convention of whether an empty codeword is allowed. Both cases are outside the original statement here. Encoding groups of symbols changes the source alphabet and the optimization problem; the minimum here concerns one source symbol per codeword.

Unique decipherability makes the map from $(X_1,\dots ,X_m)$ to the concatenated binary string $M$ injective. Entropy is unchanged by an injective relabelling, and memorylessness gives independence, henceGiven $L=\ell$, the string has at most $2^{\ell }$ possibilities. The entropy bound for finite alphabets therefore gives $H(M\mid L=\ell )\le \ell$. Averaging,The random length cannot simply be discarded: it can also carry information. Let ${\ell }_{\max }$ be the maximum codeword length, finite since the alphabet is finite. Since $L$ is a function of $M$ and takes at most $m{\ell }_{\max }+1$ values,Divide by $m$ and let $m\to \infty$. This proves $\boxed{\mathbb{E}|c(X)|\ge H(X)}$. The conclusion also covers a deterministic source; the source's lowercase $x$ in its final expectation denotes the random source letter.

First assume a full-support finite distribution, as stated above. Let $L$ be the largest codeword length and take a tree leaf at depth $L$. Every existing tree child of its tree parent must also be a tree leaf: an internal tree child would have a descendant deeper than $L$. If the chosen tree leaf were its tree parent's only tree child, moving its symbol to that tree parent would shorten its codeword by one, preserve the prefix code property, and reduce expected codeword length by its positive probability. That contradicts optimality. The tree parent therefore has at least two tree children, both tree leaves. A second codeword has the same first $L-1$ digits and a different last digit, proving the required deepest sibling codeword property for a ternary prefix code.

For the literal wording allowing zero probabilities, take $p=(1,0,0)$ and the prefix code $(0,10,110)$. Its expected codeword length is one, which is minimal: with more than one message an empty codeword is impossible, so the positive-probability message must have length at least one. Yet the deepest tree leaf $110$ has no sibling codeword. Thus positivity or an additional convention removing redundant zero-weight branches is needed.

Let $L$ again denote the largest codeword length, and assume a full-support finite distribution. The missing-branch exchange from part iii forces every internal vertex at depth at most $L-2$ to have three tree children. At depth $L-1$, all tree children are tree leaves. Part ii rules out one tree child there; the hypothesis that there is no pair of two deepest sibling codewords rules out two tree children. Thus each such tree parent also has three tree children. Every internal vertex has exactly three tree children, which is a full ternary tree, called semi-complete in this paper. The same last-level argument covers $L=1$.

Without the assumption of a full-support finite distribution the implication is false: for $p=(1,0,0)$, the optimal prefix code $(0,10,110)$ has no deepest pair of two sibling codewords, but its code tree contains vertices with a single tree child. Empty unused tree children are not vertices of the code tree.

First, the binary translation of a quaternary prefix code is still a prefix code: every translated codeword length is even, and a binary prefix relation would split into complete two-bit blocks, giving a prefix relation between the original quaternary codewords. Binary Huffman coding is optimal among binary prefix codes, soFor the other direction, let ${\ell }_i=|c_B(x_i)|$ and round these binary codeword lengths to quaternary lengths $k_i=\lceil {\ell }_i/2\rceil$. The Kraft inequality givesThe quaternary converse of the Kraft inequality supplies a quaternary prefix code with lengths $k_i$. Optimality of the quaternary Huffman code then impliesThus binary translation of an optimal quaternary code costs at most one extra bit per source symbol:The quaternary Huffman code uses the usual adjustment of adding zero-weight dummy leaves when needed. If the alphabet has one symbol, both optimal codes may use the empty codeword, giving the trivial endpoint.

Use the balancing fact proved by the exchange argument in part d: every leaf of an optimal tree has depth $s-1$ or $s$. A full binary tree with this property has all $2^{s-1}$ possible vertices at level $s-1$; at least one of these is split into two deepest leaves. ThusThese inequalities characterize the maximum codeword length exactly:In the suggested notation $m=a{2}^k$, $1\le a<2$, this is $s=k$ for $a=1$ and $s=k+1$ for $1<a<2$. The distinction at a power of two is important.

The prefix tree of a code has vertices corresponding to prefixes of codewords, with one edge for each next symbol. The root represents the empty word. In a prefix code, complete codewords are leaves, and their depths are their codeword lengths.

// Target: computer-science.bigb

For a finite source alphabet with at least two symbols and strictly positive weights, every ternary prefix code minimizing weighted codeword length has all internal vertices of outdegree three, except possibly one of outdegree two whose tree children are deepest tree leaves.

To prove this, let $L$ be the greatest tree leaf depth. A missing tree child at any depth $n<L$ would permit moving a deepest tree leaf into that vacant branch, strictly reducing its positive weighted cost. Thus all internal vertices above depth $L-1$ have three tree children. Tree parents at depth $L-1$ have only tree leaves as tree children; one tree child would permit contraction and strict improvement. If two such tree parents each had two tree children, move one tree child of the second into the first tree parent's third slot, preserving its depth, and contract the second tree parent's remaining tree child. This again strictly improves cost. There is therefore at most one binary tree parent. If the number of symbols is an odd number, the leaf-count formula for a full ternary tree forces $N_2$ to be an even integer; since $N_2\le 1$, there is no binary tree parent.

Strict positivity matters. For probabilities $(1,0,0)$, the prefix code $(0,10,110)$ minimizes expected codeword length at one trit, yet has unary vertices and a deepest tree leaf without a sibling codeword. Removing or rearranging zero-weight branches can select a reduced minimizer, but arbitrary minimizers need not have the positive-weight shape.

For $m\ge 2$ equiprobable symbols, the maximum codeword length of a binary Huffman code is $s=\lceil {\log }_{2}m\rceil$. Exactly $2^s-m$ codewords have length $s-1$ and $2m-2^s$ have length $s$. The balancing exchange for a uniform optimal prefix code restricts the depths to these two levels; counting leaves and using equality in the Kraft inequality determine the numbers.

// Target: probability-and-statistics.bigb