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:

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.

A binary code assigns a finite binary word $c_k$ to each source symbol $x_k$. In the ordinary unframed convention these codewords are nonempty. It is uniquely decodable when concatenation gives an injective map from finite symbol strings to bit strings:The decoder can recover the entire symbol sequence without being told where codewords end. This is stronger than merely assigning distinct words to individual symbols.

The given logarithmic moment iswhere the $r=1$ term is zero. It is attained by the positive distributionwhose probabilities sum to one. Write $A=2/[n(n+1)]$, so ${\log }_2{q}_r={\log }_{2}A+{\log }_{2}r$. For any distribution $p$ with the required logarithmic moment,Consequently the unique maximizer and its entropy areThe increasing weights are consistent with the prescribed moment; they need not be a decreasing power law.

Normalize the candidate distribution by settingThe supplied finite sum gives its meanThus it meets the constraint. Since ${\log }_2{q}_r={\log }_{2}c-r$, every other distribution $p$ with mean $m$ satisfiesNonnegativity and the equality case in part (a) proveThe maximum is unique; the entropy comparison uses the fixed mean rather than an unconstrained optimization.

For the uniform distribution $u_r=1/n$, direct expansion givesPart (a) therefore proveswith equality exactly for $p_X(r)=1/n$ for every $r$. Thus the uniform distribution is the unique entropy maximizer.

Let the input law again be $(s,t,u)$. The second output symbol has probability $1/2$ regardless of the input, and the two remaining output probabilities sum to $1/2$. Hencewith equality when the first and third output symbols each have probability $1/4$. The row entropies are $1,3/2,1$, soTake $t=0$ and $s=u=1/2$. The output is $(1/4,1/2,1/4)$ and both bounds are attained. ThereforeThe equality conditions also show uniqueness of the optimum input law. The middle row is the average of the outer rows and carries extra conditional entropy without introducing a new output law; removing a redundant input symbol from a channel explains why it need not be used.

Every row has Shannon entropy $1$, so $H(Y\mid X)=1$ for every input law. Since the output alphabet has three symbols, Gibbs inequality gives $H(Y)\le {\log }_{2}3$. The uniform input givesso it attains the upper bound. ThereforeUniform output is necessary for equality in the entropy bound, and the three displayed equations then force the uniform input, so this optimum input law is unique.

Let the input probabilities be $(s,t,u)$ and put $v=s+u=1-t$. The output distribution and conditional entropy areFor fixed $v$, the first and third output masses sum to $v/2$. Their entropy is maximized when they are equal, so $s=u=v/2$. Equivalently, if $v>0$,The same bound holds at $v=0$ by continuity. Therefore $I(X;Y)\le h_2(v/2)-v/2$, with equality for symmetric outer input probabilities. Writing $z=v/2\in [0,1/2]$, differentiate:The unique zero is $z=1/3$; strict concavity makes it the global maximum. Thus $v=2/3$ andThe optimum output is $(1/6,2/3,1/6)$.

Every positive atom has probability at most $\Pi$, so $-{\log }_{2}p(x)\ge -{\log }_2\Pi$. Averaging yieldsFor $0<\Pi \le 1/2$, the supplied inequality $4\Pi \le 4^{\Pi }$ gives $2+{\log }_2\Pi \le 2\Pi$. Rearranging provesThe two regimes combine into the entropy lower bound from the largest atom, valid for every finite probability distribution.

Choose a most probable symbol $x_{\ast }$, and let $B=1_{\{X=x_{\ast }\}}$. Its binary entropy isSince $B$ is a function of $X$, part (a)(ii) gives $H(X)\ge h_2(\Pi )$. On $[1/2,1]$, the concave function $h_2$ lies above the chord joining $(1/2,1)$ and $(1,0)$. That chord has height $2(1-\Pi )$. ThereforeThe endpoint $\Pi =1$ is included by continuity and corresponds to a deterministic source.

Set $Z=g(X)$. Given $X$, the value of $Z$ is certain, so $H(Z\mid X)=0$. Applying the entropy identity in the two orders givesbecause conditional entropy is nonnegative. ConsequentlyA deterministic coarsening can merge distinguishable source outcomes, but cannot create additional Shannon entropy.

For finite-valued random vectors, write $p(x,y)=P(X=x,Y=y)$ and $p_Y(y)=P(Y=y)$. The conditional entropy is the average entropy of the posterior distributions:Equivalently, $H(X\mid Y)=-{\sum }_{x,y:p(x,y)>0}p(x,y){\log }_{2}p(x\mid y)$. Since $p(x,y)=p_Y(y)p(x\mid y)$, splitting the logarithm givesUse the usual convention $0{\log }_{2}0=0$ and omit conditionals at zero-probability outputs. The same identities hold for countable alphabets whenever the entropy sums are well-defined, without subtracting two infinite quantities.

A compact code or optimal prefix code minimizes the expected codeword length ${\sum }_x{p}_x{\ell }_x$ for the given source probabilities and coding alphabet. The relevant comparison here is among binary prefix codes. The minimum is also the minimum among uniquely decodable codes, since the Kraft-McMillan inequality permits every uniquely decodable length list to be realized by a prefix code with the same lengths.

A prefix code has no codeword that is a proper prefix of another. Its code tree therefore places source symbols at leaves. It is instantaneous because the decoder knows that a source symbol has ended as soon as its leaf is reached, without needing to inspect later transmitted symbols.

In the terminology used here, a block code assigns a distinct word of the same length to every source symbol. For a binary code with $m$ symbols this common length must satisfy $2^{\ell }\ge m$. The equal-length property is what matters in this question; elsewhere the term can also refer more generally to coding blocks of source symbols.

For each $r$, conditioning on all the other coordinates gives no greater conditional entropy than conditioning only on the preceding ones. Summing and using the chain rule for entropy gives directlyEquivalently, the left side is $n{H}_n-{\sum }_{r}H(X_{-r})$, so the same conclusion follows from Han's entropy inequality. The direct proof also covers $n=1$, interpreting conditioning on an empty vector as no conditioning.

The chain rule for entropy, with $X_r$ placed last, givesSince $X_{-r}$ includes all the preceding coordinates, conditioning monotonicity givesThis proves the first assertion for every $r$, including $r=1$. Sum over $r$: the conditional terms on the right sum to $H_n$ by the ordinary chain rule. ThusThis is Han's entropy inequality.

Factoring a joint probability into successive conditional probabilities and taking the expected negative logarithm gives the chain rule for entropy:At $r=1$ this means the unconditional entropy. Removing conditioning can only increase each term by part (a), so $H_n\le {\sum }_{r}H(X_r)$.

Write $X_{-r}$ for the vector omitting coordinate $r$. Another application of the chain rule gives $H(X_{-r}\mid X_r)=H_n-H(X_r)$. ThereforeDivide by $n-1>0$ to obtain the required averaged inequality. The case $n=1$ is excluded precisely because that denominator vanishes.

Apply Gibbs inequality to the joint distribution and the product of its marginals. Restrict to the Cartesian product of their positive supports, so the reference probabilities are strictly positive as the supplied inequality requires. Expanding givesThis proves the second inequality. For the first, apply the same argument to the conditional joint distribution of $(X,Z)$ for each $y$ with $p_Y(y)>0$, and average with those probabilities:Here the conditional support restriction again removes zero marginal probabilities. ThusThe nonnegative differences are conditional mutual information and mutual information, respectively.