Use the continuous convention $0{\log }_2(0/q)=0$. Let $S=\{r:p_r>0\}$. Applying the allowed logarithm inequality to $q_r/p_r$ for $r\in S$ givesHence $d(p,q)\ge 0$. Equality forces ${\sum }_{r\in S}{q}_r=1$. Since every $q_r$ is strictly positive, this makes $S$ the entire alphabet. Equality in every weighted logarithm inequality then forces $q_r/p_r=1$ for every $r$. Conversely $p=q$ makes every summand zero. ThusThis is Gibbs inequality for relative entropy, with zero probabilities in the first argument handled explicitly.

Fix the channel matrix $W$. The mixed input induces the mixed output $q_3=\lambda q_1+(1-\lambda )q_2$. The concavity of information entropy impliesFor completeness, the difference is $\lambda D(q_1\Vert q_3)+(1-\lambda )D(q_2\Vert q_3)\ge 0$ by Gibbs inequality, including zero coordinates with the usual conventions.

On the other hand, conditional output entropy is linear in the input law:Subtracting gives the concavity of mutual information in the input distribution:This makes maximizing mutual information over the input probability simplex a concave optimization problem: a local maximum is global. It also justifies averaging input distributions over channel symmetries when searching for an optimum, since symmetry averaging cannot lower the achieved mutual information. The channel itself is held fixed throughout.

For a finite joint distribution, the mutual information isZero-probability terms contribute zero. It measures the reduction in uncertainty about one variable upon observing the other.

A discrete memoryless channel has discrete input/output alphabets and a fixed transition matrix $W(y\mid x)$. Over successive uses it obeysThus the output at a use depends on that input and no other channel history. Its channel capacity isin bits per use for base-two logarithms. On finite alphabets the maximum exists by continuity on the probability simplex; for more general discrete alphabets one uses a supremum.

Given an output $y$ of positive probability, the ideal observer chooses a symbol maximizing the posterior:Ties may be broken arbitrarily, and the choice at an impossible output does not matter. This is maximum a posteriori decoding. It minimizes conditional error at each $y$, because a deterministic decision $x$ is correct with probability $P(X=x\mid Y=y)$; a randomized decision is a weighted average of these success probabilities and cannot exceed their maximum.

Write ${\Pi }_y={\max }_{x}P(X=x\mid Y=y)$. Then $w(y)=1-{\Pi }_y$. Applying the two cases from part (b) to the posterior distribution givesAverage with respect to the output law to obtain the conditional entropy upper bound on minimum decoding error:This is an upper bound on the optimum error probability; it does not hold for arbitrary deliberately poor decoding rules.

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.

Put $S={\sum }_{k=1}^a{2}^{-l_k}$ and let $l_{\max }$ be the largest length. Expanding $S^n$ sums $2^{-L}$ over all strings of $n$ source symbols, where $L$ is the total code length. By unique decodability, the concatenations of length $r$ in this sum are all distinct, so there are at most $2^r$ of them. Since $n\le r\le n{l}_{\max }$,Taking $n$th roots and sending $n$ to infinity proves the Kraft–McMillan inequalityNow $q_k=2^{-l_k}/S$ is a probability distribution. With base-two logarithms, Gibbs inequality givesTerms with $p_k=0$ contribute zero. ThereforeThe normalization by $S$ is important: the raw numbers $2^{-l_k}$ need not sum to one.

A binary code assigns a finite bit string to each source symbol. Use nonempty codewords for an unframed variable-length stream. The code is uniquely decodable if no two distinct finite sequences of source symbols produce the same concatenated bit string. It is a prefix-free code if no codeword is an initial segment of a different codeword.

To prove unique decoding of a prefix code, suppose two concatenations agree. Their first codewords both begin the same bit string, so the shorter is a prefix of the longer. The prefix condition forces the first codewords to be equal. Cancel them and repeat. Since the codewords are nonempty, this process ends with both symbol sequences exhausted at the same time; otherwise a nonempty remainder could not equal the empty string. Hence the source sequences agree.

The code $\{0,01\}$ is not a prefix code, since $0$ is a prefix of $01$. Nevertheless it is uniquely decodable: decode from the right. A final $1$ forces the last codeword to be $01$, whereas a final $0$ forces it to be $0$. Removing that final word recursively gives a unique parsing. Thus the converse fails.

Let $E$ record whether the second stage erased the symbol, and write its output as $Z$. The erasure marker is outside the original output alphabet, so $E$ is determined by $Z$. Independence makes $E$ independent of both $X$ and the first output $Y$. The chain rule for mutual information therefore givesThe erased branch gives zero information because its output is constant; the unerased branch has exactly the original joint input-output law. Maximizing over the same input distributions givesThis includes $p=0$ and $p=1$. It is the capacity after independent output erasure; input-dependent erasure would not justify the independence step.

Let the probability of the first input be $t$. The two equal output probabilities are $(2+t)/6$, and the third is $s=(1-t)/3$. Writing $h_2$ for the binary entropy function, the output entropy is $h_2(s)+(1-s)$, while the conditional entropy is $t+(1-t){\log }_{2}3$. ThereforeThe derivative with respect to $s$ isand the second derivative is $-1/(\ln 2s(1-s))<0$ in the interior. Thus the unique stationary point is the global maximum. It occurs at $s=4/31$, soThe capacity itself is $\boxed{C={\log }_2(31/27)}$. The maximization is over $t$, not over arbitrary output distributions; $s=(1-t)/3$ keeps the feasible outputs explicit.

For finite-valued variables, mutual information isTerms of zero joint probability are zero. A discrete memoryless channel has fixed transition probabilities $W(y\mid x)$ on finite alphabets, and conditional on an input sequence its outputs are independent with the product law ${\prod }_{i}W(y_i\mid x_i)$. Its channel capacity isbits per channel use. The maximum is over all input distributions, with the transition law held fixed.

Suppose every sum of two distinct probabilities exceeds every third probability. If an optimal code were not a block code, part (b) gives two deepest sibling leaves $x,y$ at depth $L>n$ and a leaf $z$ at depth $\ell <n$. Replace the sibling pair by a leaf labelled $z$, and replace the former $z$ leaf by two children labelled $x,y$. The resulting tree is still a prefix tree, and other word lengths are unchanged. The change in expected length isHere $L-\ell -1\ge 1$. This contradicts optimality. Thus every optimal code is a block code.

Conversely, suppose distinct $x,y,z$ satisfy $p_x+p_y\le p_z$. Starting with the complete length-$n$ code, arrange $x,y$ as a sibling pair, which is possible by permuting the source labels. Its parent at depth $n-1$ does not contain $z$. Label that parent $z$, and split the old $z$ leaf into children $x,y$. This gives lengths $n-1$ for $z$, $n+1$ for $x,y$, and $n$ otherwise, with expected lengthIf the optimal mean length is below $n$, no optimal code can be a block code: any injective binary block code for $2^n$ symbols has length at least $n$. If the optimal mean is $n$, the constructed non-block code itself is optimal. In either case there is an optimal non-block code. This proves the reverse implication, including the equality case, and hence the strict inequality in the criterion is necessary.

This is the optimality of a fixed-length code for a power-of-two alphabet.

Every internal node of an optimal binary prefix tree has two children. If one had only one child, remove that one-edge detour from all descendant words. Prefix-freeness is preserved and at least one positive-probability word becomes shorter, strictly lowering the expected length. Thus the tree is full.

Take a leaf at maximum depth $L$. Its sibling exists because the tree is full. That sibling cannot be an internal node, since a descendant would be deeper than $L$. Hence it is another leaf at depth $L$, and the corresponding codewords differ only in their final bit. This is the deepest sibling property of an optimal prefix code.

A finite full binary tree satisfies Kraft equality, ${\sum }_x{2}^{-{\ell }_x}=1$, by dividing mass equally down each branch from the root. If all $2^n$ lengths were at least $n$, with at least one strictly greater, that sum would be less than $2^n{2}^{-n}=1$, a contradiction. Since the code is not a block code, the alternative that all lengths equal $n$ is excluded. Therefore some word has length below $n$. Also a longest word must have length above $n$: if all lengths were at most $n$ and some shorter, the Kraft sum would exceed one.