Let $\bar{\ell }=\mathbb{E}|c(X)|$. The Huffman encoder emits an average of $w\bar{\ell }$ binary digits per minute. Shannon's noisy-channel coding theorem states that for a discrete memoryless channel of capacity $K$, every information rate strictly below $K$ bits per use is achievable with error probability tending to zero as block length grows; rates above $K$ are not achievable for unrestricted messages.

Thus a channel code carrying the Huffman bitstream reliably with buffering and arbitrarily long blocks can be chosen wheneverThe strict inequality supplies positive coding and buffering slack. Huffman's expected-length bound is $H(X)\le \bar{\ell }<H(X)+1$ for a nontrivial finite source. Therefore the simpler bound $r>w(H(X)+1)/K$ is sufficient without knowing its exact Huffman lengths.

Distinguish this bitstream construction from the absolute source-channel limit. The noiseless source coding theorem permits long source blocks to be compressed to any rate above $H(X)$ bits per source symbol, with arbitrarily small overhead. Together with channel coding, this gives the sharper limiting requirement $rK>wH(X)$; $rK<wH(X)$ is impossible by the source-channel converse. Further compression can exploit redundancy remaining in a single-symbol Huffman stream, so $w\bar{\ell }/K$ need not be the universal minimum channel symbol rate. At $K=0$ a positive-entropy source cannot be sent reliably at a finite rate.

The entropy isTo construct a Huffman code, work with integer weights $2,2,3,4,5$. Merge the two twos to make four. Of the remaining weights $3,4,4,5$, merge three with the original four to make seven, and merge the new four with five to make nine. Finally merge seven with nine. Resolving the tie in this way gives, for example,This is a prefix code and Huffman's optimality theorem makes it optimal. Its expected length isDifferent choices at a tied merge can give different optimal codewords with the same expected length.

Unique decipherability makes the map from $(X_1,\dots ,X_m)$ to the concatenated binary string $M$ injective. Entropy is unchanged by an injective relabelling, and memorylessness gives independence, henceGiven $L=\ell$, the string has at most $2^{\ell }$ possibilities. The entropy bound for finite alphabets therefore gives $H(M\mid L=\ell )\le \ell$. Averaging,The random length cannot simply be discarded: it can also carry information. Let ${\ell }_{\max }$ be the maximum codeword length, finite since the alphabet is finite. Since $L$ is a function of $M$ and takes at most $m{\ell }_{\max }+1$ values,Divide by $m$ and let $m\to \infty$. This proves $\boxed{\mathbb{E}|c(X)|\ge H(X)}$. The conclusion also covers a deterministic source; the source's lowercase $x$ in its final expectation denotes the random source letter.

Define $H(X\mid Y)={\sum }_y\mathbb{P}(Y=y)H(X\mid Y=y)$. The joint entropy identity $H(X,Y)=H(Y)+H(X\mid Y)$ follows by writing $p_{xy}=q_y{p}_{x\mid y}$ and expanding its logarithm. If $Y=g(X)$, then $H(Y\mid X)=0$ and $H(X,Y)=H(X)$, giving the desired decomposition.

Group the first two symbols together and keep the third separate. If $c<1$, the identity becomeswhere $h(t)=-t{\log }_{2}t-(1-t){\log }_2(1-t)$. Binary entropy is at most one, with equality precisely at $1/2$. HenceEquality holds exactly when $a=b=(1-c)/2$. When $c=1$, $a=b=0$, so the same conclusion holds at the boundary.

For a finite probability distribution,with $0{\log }_{2}0=0$. If the positive support has size $s\le n$, apply the given strict Jensen inequality to the random variable $Z=1/p_X$:Equality requires $s=n$ and $Z$ constant almost surely, so all probabilities are $1/n$. Conversely the uniform distribution attains this bound. Thus $\boxed{H(X)\le {\log }_{2}n}$, with exactly that equality case.

The conditional output distributions are permutations of the same triple, so both conditional entropies equalWith input probability $p$, the three output probabilities are $q_1=(2-p)/6$, $q_2=(1+2p)/6$, and $q_3=(3-p)/6$. ThereforeDifferentiating, the constant terms cancel because $\sum q_j^{\prime }=0$:Thus there is a unique maximum. Its stationary equation reduces to $3p^2+9p-5=0$, whose root in $[0,1]$ isThe other root is negative; strict concavity proves this is the global maximum.

A radius-$r$ Hamming decoder outputs the unique codeword within distance $r$ of the received word, if there is one. Ambiguous cases and absent candidates can be declared errors, or assigned arbitrarily for an error bound. The average error is the mean of the conditional error probabilities over the equally likely transmitted messages.

Let $V_n(r)={\sum }_{j=0}^r\left(\genfrac{}{}{0ex}{}{n}{j}\right)$ be the size of a Hamming ball. For any transmitted random codeword, the channel noise weight is $U\sim \mathrm{Bin}(n,p)$. Decoding can fail only if $U>r$ or another codeword lies within distance $r$ of the output. Conditional on the output, each independently sampled competing codeword is still uniform on the whole word space, so has probability $2^{-n}{V}_n(r)$ of lying in that ball. A union bound yieldsThis is an average over the random code construction as well as over messages and noise. It implies existence of at least one deterministic codebook with average error no greater than this bound, rather than asserting the same inequality for every randomly sampled book.

Choose a target rate $R<1-h(p)$ and a small $\delta >0$ such that $p+\delta <1/2$ and $R<1-h(p+\delta )$. Let $M_n=\lfloor 2^{nR}\rfloor$ and $r=\lfloor n(p+\delta )\rfloor$. The standard Hamming-volume estimate is $V_n(r)\le 2^{nh(r/n)}$: for $s=r/n\le 1/2$, each binomial probability term $s^j(1-s{)}^{n-j}$ with $j\le r$ is at least $s^r(1-s{)}^{n-r}$, and summing proves this bound. Thus the union-bound term decays exponentially, while $P(U>r)\to 0$ by the law of large numbers or a Chernoff bound.

There exists a $2M_n$-message book with average error ${\epsilon }_n\to 0$. At least half its messages have individual error at most $2{\epsilon }_n$, by Markov's inequality on the uniformly chosen message. Keep $M_n$ of these and discard the rest. Restricting the decoder's candidate set cannot spoil a previously unique successful decoding. The retained book therefore has maximum error at most $2{\epsilon }_n\to 0$. For large $n$ its retained codewords must be distinct: identical words could not both have conditional error below one half. This expurgation of a codebook proves reliable communication at every rate below $1-h(p)$, while converting an average-error estimate into the requested maximum-error conclusion.

With equally likely codewords, the prior factor in the ideal-observer criterion is constant, so it agrees with maximum likelihood. On the binary symmetric channel,For $0<p<1/2$ this is strictly decreasing in Hamming distance, so the likelihood maximizers are precisely the nearest codewords. With the same tie convention all three decoders therefore agree. At $p=0$ every possible received word equals its transmitted codeword, and the rules agree on all positive-probability outputs; outputs having zero probability need no posterior assignment.

Exchanging the first and third inputs, together with the corresponding outputs, leaves the channel unchanged. Concavity therefore shows that averaging an input distribution with its exchanged distribution cannot reduce mutual information. We may take input probabilities $(a,1-2a,a)$.

For $p<1$, put $b=1-p$ and $t=2ab$, so $0\le t\le b$. The output distribution is $(t/2,1-t,t/2)$ and the mean conditional output Shannon entropy is $2ah(p)=th(p)/b$. HenceIts strict concavity gives the unique stationary value $t_{\ast }=[1+2^{h(p)/b-1}{]}^{-1}$. This lies in the allowed interval: for $0<p<1$, the derivative at $t=b$ is $({\log }_{2}p+b)/b<0$, while it tends to positive infinity at zero. At $p=0$ the stationary value is $2/3<1$ directly. Consequently an achieving input distribution isThe resulting capacity is $C={\log }_2(1+2^{1-h(p)/(1-p)})$. In particular at $p=1/2$, $a=1/3$ andAt $p=1$ all outputs are the middle symbol, so $C=0$ and every input distribution achieves it; the divided formula is not used at that endpoint.

Gibbs inequality makes mutual information nonnegative, so $C\ge 0$. The two conditional-Shannon entropy expressions giveEach Shannon entropy is bounded by the base-two logarithm of its alphabet size. Maximizing over the input distribution therefore gives $\boxed{0\le C\le {\log }_{2}m}$ for the smaller size $m$.

The channel matrix has entries $M_{xy}=P(Y=y\mid X=x)$, with nonnegative entries and each row summing to one. For an input distribution $\pi$, it induces the joint law $P(X=x,Y=y)={\pi }_x{M}_{xy}$. Its capacity in bits per use isOn finite alphabets the maximum exists by continuity on the compact probability simplex.