Derive: Information and Compression

Write each entropy as a sum over the joint table. The marginal $H(A)$ is $$H(A)=\sum _{a,b}p(a,b){\log }_2\frac{1}{p(a)},$$ and $H(B)$ is the same with $p(b)$. The joint entropy is $$H(A,B)=\sum _{a,b}p(a,b){\log }_2\frac{1}{p(a,b)}.$$ Substituting into $I=H(A)+H(B)-H(A,B)$ gives $$I(A;B)=\sum _{a,b}p(a,b)\left[{\log }_2\frac{1}{p(a)}+{\log }_2\frac{1}{p(b)}-{\log }_2\frac{1}{p(a,b)}\right].$$ The bracket is the logarithm of a product divided by a product, so $$I(A;B)=\sum _{a,b}p(a,b){\log }_2\frac{p(a,b)}{p(a)p(b)}.$$ This is exactly the KL divergence between the true joint table and the product of the marginals.

For non-negativity, work in natural logarithms and call the right-hand side $D$. Then $$-D=\sum _{a,b}p(a,b)\ln \frac{p(a)p(b)}{p(a,b)}\le \ln \sum _{a,b}p(a)p(b)=\ln 1=0,$$ where the inequality is $\ln x\le x-1$ applied to each term, or equivalently Jensen's inequality for the concave logarithm. Hence $D\ge 0$. Equality in $\ln x\le x-1$ holds only at $x=1$, so every cell with $p(a,b)>0$ must satisfy $p(a,b)=p(a)p(b)$. The two distributions share their marginals, so the remaining cells are forced to match as well. That is the definition of independence.

Now evaluate the table. The cells are $0.5$, $0.1$, $0.1$ and $0.3$. Both marginals are $0.6$ and $0.4$, so $$H(A)=H(B)=H(0.6)=\mathrm{0.970951.}$$ The joint entropy is $$H(A,B)=-\left(0.5{\log }_{2}0.5+0.1{\log }_{2}0.1+0.1{\log }_{2}0.1+0.3{\log }_{2}0.3\right).$$ The terms are $0.5$, $0.332193$, $0.332193$ and $0.521090$, so $$H(A,B)=\mathrm{1.685475.}$$ Therefore $$I(A;B)=0.970951+0.970951-1.685475=0.256427,$$ which rounds to $0.2564$. The product model assigns $0.36$, $0.24$, $0.24$ and $0.16$ to the four cells. The KL divergence from the true table to that product is $$0.5{\log }_2\frac{0.5}{0.36}+0.1{\log }_2\frac{0.1}{0.24}+0.1{\log }_2\frac{0.1}{0.24}+0.3{\log }_2\frac{0.3}{0.16},$$ which equals the same $0.2564$. Section 16.2 defines the divergence; section 16.3 uses it to read mutual information as the cost of assuming independence. The derivation shows that the two sections describe one quantity, not two.

A prefix code for two symbols cannot give both symbols the empty codeword, and it cannot give one symbol the codeword that begins the other. The assignment with the smallest average length is one bit each, for example 0 and 1. Suppose one symbol receives a codeword of length at least two. Since the other symbol needs a nonempty codeword and cannot be a prefix of the first, its length is at least one. If the longer codeword belongs to the less probable symbol, the average length is at least $$p(1)+(1-p)(2)=2-p>1$$ for $p<1$. If the longer codeword belongs to the more probable symbol, the average is even larger. The minimum is therefore attained by the one-bit-each code, so $$L=1.$$ The entropy is the binary entropy $$H(p)=-p{\log }_{2}p-(1-p){\log }_2(1-p).$$ The gap is $$L-H(p)=1-H(p).$$ As $p\to 1$, both terms of $H(p)$ tend to zero, so $H(p)\to 0$ and the gap tends to 1 bit. At $p=0.99$, $$H(0.99)=-0.99{\log }_{2}0.99-0.01{\log }_2\mathrm{0.01.}$$ The terms are $0.99(0.0145)=0.0144$ and $0.01(6.6439)=0.0664$, so $$H(0.99)=0.0808,$$ and the gap is $$1-0.0808=\mathrm{0.9192.}$$ The result is an edge case for the claim that Huffman stays close to the entropy. The bound $H\le L<H+1$ allows a gap of almost one full bit, and this source approaches that ceiling. The bound is not contradicted: $0.9192<1$, and the strict inequality holds for every $p<1$. The gap reaches 1 only in the limit. At exactly $p=1$ the second symbol never occurs, so the source has one symbol and a zero-bit code achieves $L=H=0$; the discontinuity at the endpoint is the reason the strict bound is stated for a genuine two-symbol source. A claim that Huffman is "within a bit" is correct, and a claim that it is close in relative terms is false when the entropy is near zero.

The output differs from the input when exactly one channel flips. The two cases are mutually exclusive, so the effective flip probability is $$f=f_1(1-f_2)+(1-f_1)f_2.$$ Substituting $f_1=0.1$ and $f_2=0.2$ gives $$f=0.1(0.8)+0.9(0.2)=0.08+0.18=\mathrm{0.26.}$$ The composition of two binary symmetric channels is another binary symmetric channel, so section 16.6's formula applies: $$C_{\text{series}}=1-H(0.26).$$ The noise entropy is $$H(0.26)=-0.26{\log }_{2}0.26-0.74{\log }_2\mathrm{0.74.}$$ The terms are $0.26(1.9434)=0.5053$ and $0.74(0.4344)=0.3215$, so $$H(0.26)=0.8267$$ and $$C_{\text{series}}=1-0.8267=\mathrm{0.1733.}$$ Used alone, the channels have capacities $$C_1=1-H(0.1)=0.5310,C_2=1-H(0.2)=\mathrm{0.2781.}$$ A use of the pair spends two channel uses, so the rate per individual channel use is $$\frac{0.1733}{2}=\mathrm{0.0866.}$$ That is below both $C_1$ and $C_2$. The effective flip probability $0.26$ is above either individual flip probability. The second channel can undo a flip, but it can also add one, and for these two flip probabilities the adding cases are more likely than the undoing case.

Capacity is not additive. Two perfect channels in series still carry one bit per use, not two, because the second use sees the same bit rather than a new one. A second noisy channel cannot create information about the original bit; it can only preserve or destroy what is left. Chaining channels therefore adds noise and can only lower the rate. The numbers show the size of the loss for this pair, and the formula shows that the loss depends on the entropies rather than on the raw flip probabilities.