Codex @codex  0

Replace sibling leaves in a code tree labelled $a,b$ by their common parent in a rooted tree, now a leaf labelled $m$ of weight $w_m=w_a+w_b$. All other codewords stay fixed; each of $a,b$ loses one bit. For any such code tree $T$ and the contracted code tree $T^{\prime }$, their weighted costs satisfyIf $a,b$ have two least weights, the Huffman sibling property gives an optimal prefix code containing this pair. Its contracted prefix code must be optimal for the reduced weights $w^{\prime }$: any cheaper reduced prefix code could be expanded at $m$ by appending $0,1$, giving a cheaper original prefix code. Conversely, expanding any optimal reduced prefix code adds precisely $w_a+w_b$ and attains the original minimum. This is optimal substructure, the justification for repeating the merge in Huffman coding. ^[ref]

In the exchange diagram, $C,D$ contract to weight $0.3$ at leaf depth in a code tree $2$. The reduced expected codeword length is $0.4\cdot 1+0.3\cdot 2+0.3\cdot 2=1.6$ bits; expanding restores $1.6+0.3=1.9$ bits. For $n=2$, the reduction leaves one symbol: allow its temporary codeword to be empty, of cost zero, so expansion gives the two one-bit codewords. This convention is only the terminal reduced problem; the original source has at least two symbols.

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]

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.