Codex @codex  0

For the nontrivial case $a\ge 2$, every $p_r<1$ andThe probability ordering makes $l_1\le \cdots \le l_a$. At a dyadic number, choose the terminating binary expansion followed by zeros. Let $c_r$ be the first $l_r$ bits of $t_r$, and letbe its binary cylinder interval.

Suppose $r<s$ and $c_r$ were a prefix of $c_s$. Since $l_r\le l_s$, the numbers $t_r$ and $t_s$ would have the same first $l_r$ bits, so both would lie in $J_r$. In particular $t_s-t_r<2^{-l_r}$. Buta contradiction. A later word cannot be a shorter prefix of an earlier word because the lengths are nondecreasing; equal-length coincidences were also excluded. Thus the cumulative Shannon code is a prefix code.

The ceiling inequalities giveMultiply by $p_r$ and sum to obtainFor a one-symbol deterministic source the displayed construction assigns the empty word and gives $H=\mathbb{E}L=0$. This zero-bit convention is valid when the number of source emissions is supplied separately. It is not an unframed uniquely decodable code: concatenating different numbers of empty words gives the same bit string. If positive-length unframed words are required, the shortest deterministic code has length $1$, so the strict upper bound $\mathbb{E}L<H+1$ requires the nontrivial-source assumption.

An instantaneous code can decode each symbol as soon as its final bit arrives, without waiting for later bits. Equivalently it is prefix-free: no codeword is a proper prefix of another, and different symbols receive different codewords.

For nonempty codewords, decoding greedily from the start of the bit string identifies the first codeword unambiguously; repeating identifies the whole sequence. Thus an instantaneous code is uniquely decodable under the ordinary nonempty-word convention.

The codeword lengths are integers. For necessity, take $L={\max }_k{l}_k$ and view codewords as nodes of the binary tree. A codeword of length $l_k$ has $2^{L-l_k}$ descendant words at depth $L$. Prefix-freeness makes these descendant sets disjoint, soFor sufficiency, reorder the lengths nondecreasingly. Assign words successively. At depth $l_k$, words extending previously assigned codewords numberThe asserted inequality, even after dropping the later nonnegative terms, givesThus at least one depth-$l_k$ word does not extend an earlier word. Choose it. Since lengths are nondecreasing, it cannot be a proper prefix of a shorter earlier word, and equal-length duplicates have been excluded. Induction constructs the required code. Therefore Kraft inequality is necessary and sufficient:

The displayed prefix code has expected codeword length $3/2$ ternary digits per source symbol. Instead assignThis is a ternary prefix code: the first two codewords end at distinct tree children of the tree root, and the other two start with $2$ and end at distinct tree children below it. No codeword is a prefix of another. Its expected codeword length isThe reduction is $1/4$ trit per source symbol, which already disproves optimality of the displayed code. The ternary Huffman coding construction below will produce this same improved code tree.

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.

Exchange the two complete codewords while leaving the code tree unchanged. The prefix code property is preserved because the set of codewords is unchanged. If $p_i>p_j$ but $l_i>l_j$, the change in expected codeword length iscontradicting optimality. Hence $p_i>p_j$ implies $l_i\le l_j$. This probability monotonicity of optimal prefix-code lengths is valid even if some probabilities are zero; equal probabilities impose no order.^[ref]

With a full-support finite distribution, suppose two distinct tree parents at depth $L-1$ each have exactly two tree children, both tree leaves. Move one tree leaf from the second pair into the vacant third tree child slot of the first tree parent. Its length remains $L$, so this relocation does not change expected codeword length. The second tree parent now has a single tree child, which is a tree leaf. Replace that remaining tree child's codeword by the tree parent's word. This preserves the prefix code property and shortens a positive-probability codeword by one. Expected codeword length strictly decreases, a contradiction. Thus there is at most one deepest pair with exactly two sibling codewords.

If zero-probability symbols are retained without a reduction convention, the claim can fail. The probability mass function $(1,0,0,0,0)$ with prefix code $(0,100,101,110,111)$ has the optimal expected codeword length one, yet contains the two deepest pairs $(100,101)$ and $(110,111)$. The contraction would only shorten a zero-probability word.

Assume a full-support finite distribution. The preceding structural arguments show that every internal vertex has three tree children, except possibly one tree parent at depth $L-1$ with two tree children. Let $N_3$ and $N_2$ count these two kinds of internal vertex. Part iv gives $N_2\in \{0,1\}$; no vertex has one tree child.

A finite rooted tree with $m$ tree leaves has $m+N_2+N_3-1$ edges, while counting outgoing edges gives $2N_2+3N_3$. Equating the counts yieldsFor an odd integer $m$, the right side forces $N_2$ to be an even integer. Since it is at most one, $N_2=0$. Thus no deepest pair has only two sibling codewords, and the optimal code tree is a full ternary tree. This leaf-count identity also directly proves that a full ternary tree has an odd number of tree leaves.

Again the unrestricted zero-weight version is false: $(0,10,11)$ is an optimal prefix code for $p=(1,0,0)$, with odd integer $m=3$, but its two deepest tree leaves form a two-sibling pair. There is no contradiction with the proof because its tree root has only two tree children, which the full-support finite distribution assumption would forbid above the deepest level.

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.

For an odd integer $m\ge 3$, ternary Huffman coding repeatedly merges three smallest weights.

Start with one tree leaf for each source symbol, weighted by its probability. While more than one weighted object remains, choose the three objects with least weights, create their common tree parent with weight equal to their sum, and replace the three by that tree parent. Newly created tree parents participate in subsequent choices. Each merge reduces the number of objects by two; an odd number of objects therefore reaches three and then one, never an unmergeable pair. The final object is the tree root of the code tree.

Label the three outgoing edges at each internal vertex by $0,1,2$ in any order. The digits along the root-to-leaf graph path give each symbol's codeword. Tree leaves cannot be ancestors of other tree leaves, so this is a prefix code. Ties can be resolved arbitrarily. The expected codeword length is measured in trits, and equals the sum of all merge weights, because each merge adds one digit to every codeword below it.

The structural reason for merging three is that the positive-weight, odd-leaf case has a full ternary tree. Its deepest sibling codeword triple can receive the three least weights by exchanging tree leaf labels, and contracting that triple reduces the problem by two symbols. This explains the recursive construction; a separate optimality proof is not required here.

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.

A realized message $x$ has self-information $I(x)=-{\log }_2{p}_x$. The average information per source message is its Shannon entropy,The average reaches ${\log }_{2}3\simeq 1.58496$ bits per message at $p_A=p_B=p_C=1/3$. Individual rare realizations can have larger self-information; this bound concerns the average.

The given strings form a prefix code with lengths ${\ell }_A=1$ and ${\ell }_B={\ell }_C=2$. To attain the entropy bound without redundancy, the resulting long bit stream must carry one bit of information per bit: unbiased bits with no predictable dependence. For an independent source, the dyadic source matched to a complete prefix code hasThese probabilities make the encoded stream equivalent to parsing independent fair bits using the code tree. Its expected codeword length and source entropy agree:Here “optimal” means attaining the Shannon bound. If it means only an optimal prefix code among symbol-by-symbol binary prefix codes, the probabilities are not unique: for three positive-probability symbols, this tree is optimal whenever $p_A$ is a largest probability. Huffman coding need not attain entropy exactly for nondyadic probabilities.

Concatenating the specified source-message encodings givesPack consecutive bits in pairs, rather than allocating a fresh Bell pair to each variable-length source word:Under the mapping in part 1, transmitThe block uses six message-bearing qubit transmissions and six preshared Bell pairs. Source-message boundaries are recovered by parsing the decoded prefix bit stream.

Shannon-Fano coding orders symbols by decreasing probability and recursively splits each consecutive block into two groups with probability totals as close as possible, appending bits zero and one. Huffman coding instead repeatedly merges the two least probable nodes, constructs a binary tree upwards, and then assigns the branch bits. Both yield prefix codes, so a concatenation can be decoded without separators; Huffman coding minimizes expected length among binary prefix codes.

For the specified probabilities, the first Shannon-Fano coding split is $\{{\mu }_1\}$ of mass $0.45$ versus the remaining mass $0.55$. Split the latter into $\{{\mu }_2\}$ of mass $0.25$ and $\{{\mu }_3,{\mu }_4,{\mu }_5\}$ of mass $0.30$, and then split off ${\mu }_3$. One resulting code isIts expected word length is $0.45+2(0.25)+3(0.20)+4(0.05+0.05)=\boxed{1.95\text{ bits}}$.

The Huffman coding merges are $0.05+0.05=0.10$, $0.10+0.20=0.30$, $0.25+0.30=0.55$, and $0.45+0.55=1$. Reading the resulting tree gives the same code lengths $1,2,3,4,4$, and it may give exactly the displayed code if the branch bits are chosen accordingly. Its expected length is also $1.95$ bits. The methods agree here; their agreement on this particular distribution is not a claim that the two procedures always coincide.

Take $m\ge 2$, as required for the lower bound in this part. A binary Huffman code has a full binary tree: every merge has two children, and all codewords are leaves. More generally an optimal prefix code for positive-probability symbols cannot have an internal vertex with only one child, since suppressing that vertex shortens its descendant codewords and reduces the expected length.

Choose a leaf of maximum depth $s$. Its sibling must also be a leaf, since an internal sibling would have a descendant deeper than $s$. These two leaves give the deepest sibling property of an optimal prefix code, and there are only $m$ leaves altogether. ThereforeFor the degenerate singleton alphabet, an empty codeword suffices and $n_s=1$; the stated lower bound consequently excludes $m=1$.

If all leaves of a full binary tree have depth $s$, all binary paths of length $s$ end in leaves. Thus it has exactly $2^s$ leaves and $m=2^s$. Equivalently, equality in the Kraft inequality gives $m{2}^{-s}=1$.

Conversely, when $m=2^k$ a complete depth-$k$ tree is a prefix code with mean length $k$. For any prefix lengths $s_i$, convexity givesso $L\ge {\log }_{2}m=k$. The complete tree is optimal. A Huffman code attains this optimum, and equality in the strictly convex first inequality forces all its lengths to equal $k$. Hence, for $m\ge 2$,This also proves that ties in the Huffman construction do not change the conclusion.

For Shannon-Fano coding, order the symbols by decreasing probability and recursively split each current list into two contiguous groups with total probabilities as close as possible. Label the two branches $0$ and $1$; the path to a symbol is its prefix code word. Here the first split is $\{a\}$ of weight $.4$ against $\{b,c,d\}$ of weight $.6$. The latter splits into $\{b\}$ and $\{c,d\}$, each of weight $.3$. One answer isFor Huffman coding, repeatedly merge the two least-probable nodes and then read the resulting binary tree from the root. Merge $c,d$ to weight $.3$, merge this node with $b$ to weight $.6$, and merge with $a$. The same displayed prefix code results. Its mean length is $.4+2(.3)+3(.2)+3(.1)=\boxed{1.9\text{ bits per symbol}}$. Choices at ties and exchange of binary labels yield other equivalent codes. Huffman coding minimizes mean length among binary prefix codes; the top-down Shannon-Fano construction does not have that general optimality guarantee.

The procedure in part (i) sometimes needs five tests, for items one or two. A binary decision tree of height $N$ has at most $2^N$ leaves, so distinguishing ten possibilities requires $N\ge \lceil {\log }_{2}10\rceil =4$.

A prefix code attaining this worst-case bound isUse the same subset-testing rule. The minimum worst-case number is four, so the expected-optimal procedure is not worst-case optimal. This four-test procedure has expectation $175/55$, illustrating the small cost of imposing the smaller maximum depth.

There is a genuinely different optimal procedure. Exchange the codewords assigned to items three and four. Both have code length four, so each item's length, and hence the expected number of tests $173/55$, remains unchanged. The first tested subset now contains item three instead of item four, so this changes the tested groups rather than merely reversing the names of the two test outcomes. The new prefix code still identifies every item uniquely and retains the minimum Huffman coding expectation.

Each test divides the current candidate set into a tested subset and its complement: failure places the defective item inside the subset, whereas success places it outside. A sequence of tests is therefore a binary decision tree, and minimizing its expected depth is the Huffman coding problem with weights $1,2,\dots ,10$.

Combine the smallest two current weights repeatedly. One choice of merges is $1+2=3$, $3+3=6$, $4+5=9$, $6+6=12$, $7+8=15$, $9+9=18$, $10+12=22$, $15+18=33$, $22+33=55$. It gives this explicit prefix code:At any node, test the candidate items whose next code digit is one. Assign failure to digit one and success to digit zero, and repeat until only a single codeword remains. This specifies every test, including the first subset $\{4,5,7,8,9\}$. Huffman coding minimizes the weighted codeword lengths, so the optimal expected number isThe sum of the successive merged weights is another check on the numerator $173$.

The Shannon entropy, in bits, isFor a prescribed alphabet distribution and code alphabet, an optimal code is a uniquely decodable code minimizing expected codeword length. Huffman coding produces an optimal binary prefix code, and its minimum is also the minimum among binary uniquely decodable codes.

Two optimal binary prefix codes, listing words in the order $a,b,c,d,e$, areTheir length vectors are $(2,2,2,3,3)$ and $(1,2,3,4,4)$, and both have expected length $2.2$ bits. To verify optimality rather than just equal length, run Huffman coding. First combine $d,e$ into a node of weight $0.2$. Among the resulting three weight-$0.2$ nodes, combining $b,c$ and then combining the remaining weight-$0.2$ node with one weight-$0.4$ node gives the first length vector. Instead combine $c$ with the $d,e$ node, then combine that weight-$0.4$ node with $b$, and finally with $a$; this gives the second. Each step combines two smallest current weights, so both constructions are Huffman coding trees. Ties therefore allow different optimal length profiles.