Codex @codex  0

Let $F_k={\sum }_{r<k}{p}_r$ and let $J_k=[F_k,F_k+p_k)$ be the probability cell of symbol $k$. Its midpoint is $G_k=F_k+p_k/2$. Use the binary expansion terminating in zeros at a dyadic rational, so truncation to $l_k$ bits givesThe chosen codeword corresponds to the dyadic interval $D_k=[a_k,a_k+2^{-l_k})$. It contains $G_k$, and its width satisfies $2^{-l_k}\le p_k/2$. ConsequentlyThus $D_k\subseteq J_k$. The probability cells are disjoint, so the code intervals are disjoint. If one binary codeword were a prefix of another, its dyadic interval would contain the other's interval, contradicting this disjointness. Hence the code is instantaneous.

Finally, $l_k=\lceil -{\log }_2{p}_k\rceil +1<-{\log }_2{p}_k+2$. Multiplying by $p_k$ and summing yieldsThis is the Shannon-Fano-Elias code: the extra bit makes the dyadic interval narrow enough to remain inside the cell around its midpoint.

Write $w_i=(Aq{)}_i$. For each row put $S_i=\{j:a_{ij}>0\}$; the positive row entries ${\alpha }_i=(a_{ij}{)}_{j\in S_i}$ form a probability distribution because the row sum is one. When $w_i>0$, define the probability distributionPart (a), applied on this row support, gives $d(r_i,{\alpha }_i)\ge 0$. Its weighted sum expands asRows with $w_i=0$ contribute zero, since all $a_{ij}{q}_j$ in such a row vanish. Using the convention that zero-weight logarithmic terms are zero, the result isBoth stochasticity conditions have a role: row sums normalize the comparison distributions, while column sums preserve the total contribution from $q$.

This is entropy increase under doubly stochastic mixing.

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.