Practise: Information and Compression

The information content is $${\log }_2\frac{1}{0.04}={\log }_{2}25.$$ Because $2^4=16$ and $2^5=32$, the value lies between 4 and 5. Evaluating gives $${\log }_{2}25=4.643856\dots ,$$ which rounds to $4.644$. Section 16.1 reads the number as surprise: an outcome with probability 0.04 is about one outcome in twenty-five, and naming which one it was takes between four and five yes-or-no questions. The same symbol would carry 0 bits if it occurred every time, and more bits if it were rarer. The number describes the outcome, not the symbol's shape or its place in the alphabet.

The entropy is the weighted average of the information contents: $$H=-\left(0.4{\log }_{2}0.4+0.3{\log }_{2}0.3+0.2{\log }_{2}0.2+0.1{\log }_{2}0.1\right).$$ The four terms are $$0.4(1.32193)=0.52877,0.3(1.73697)=0.52109,$$ $$0.2(2.32193)=0.46439,0.1(3.32193)=\mathrm{0.33219.}$$ Their sum is $$0.52877+0.52109+0.46439+0.33219=1.84644,$$ which rounds to $1.846$. The answer is below ${\log }_{2}4=2$ because the symbols are not equally likely. A uniform source on four symbols would have entropy 2 bits, and section 16.1 says the uniform source is the hardest to guess. The 0.1 symbol carries more surprise per occurrence than the 0.4 symbol, because its information content is larger; its weighted contribution to the average is smaller, because it occurs less often.

The chain rule from section 16.2 is $$H(A,B)=H(B)+H(A\mid B).$$ Rearranging, $$H(A\mid B)=H(A,B)-H(B)=3.2-1.5=\mathrm{1.7.}$$ Knowing $B$ leaves 1.7 bits of uncertainty about $A$, down from 2.5 bits before $B$ was seen. The other conditional entropy is $$H(B\mid A)=3.2-2.5=0.7,$$ and the two routes agree with the chain rule run in the other order: $2.5+0.7=3.2$. Conditioning cannot raise entropy, and both conditional values sit below their corresponding marginals. The pair is not independent, because $H(A,B)=3.2$ is below $H(A)+H(B)=4$.

The definition gives $$D_{\mathrm{KL}}(p\Vert q)=0.8{\log }_2\frac{0.8}{0.5}+0.2{\log }_2\frac{0.2}{0.5}.$$ The logarithms are $${\log }_{2}1.6=0.6781,{\log }_{2}0.4=-\mathrm{1.3219.}$$ Therefore $$D_{\mathrm{KL}}(p\Vert q)=0.8(0.6781)+0.2(-1.3219)=0.5425-0.2644=\mathrm{0.2781.}$$ The positive value means that a code built for the fair distribution spends 0.2781 extra bits per symbol on data from $p$. Section 16.2 stresses that the divergence is not symmetric. Swapping the two distributions gives $$D_{\mathrm{KL}}(q\Vert p)=0.5{\log }_2\frac{0.5}{0.8}+0.5{\log }_2\frac{0.5}{0.2}=0.3219,$$ which is a different number. The divergence is zero only when the two distributions match, and it grows as the wrong distribution places less probability on the outcomes that actually occur.

Each row variable is 50–50, so $$H(A)=H(B)=1.$$ The joint entropy is $$H(A,B)=-\left(2(0.45{\log }_{2}0.45)+2(0.05{\log }_{2}0.05)\right).$$ The two distinct terms are $$0.45(1.1520)=0.5184,0.05(4.3219)=0.2161,$$ so $$H(A,B)=2(0.5184+0.2161)=\mathrm{1.4690.}$$ The mutual information is $$I(A;B)=H(A)+H(B)-H(A,B)=1+1-1.4690=\mathrm{0.5310.}$$ The variables are strongly dependent: 90 of the 100 rows sit on the main diagonal, so learning one variable removes about half a bit of uncertainty about the other. Section 16.3 also reads this number as the cost of pretending the variables are independent. The product model would assign 0.25 to every cell, and the KL divergence from the true table to that product is the same 0.5310 bits.

Merge the two least probable symbols, 0.15 and 0.10, into a leaf with probability 0.25. The leaves are now 0.30, 0.25, 0.20 and the new 0.25. Merge 0.20 with the new 0.25, giving 0.45. The leaves are 0.30, 0.25 and 0.45. Merge 0.30 with 0.25, giving 0.55, and merge 0.45 with 0.55 at the root. The lengths are $$2,2,2,3,3$$ for the symbols in the order given. The average length is $$L=0.30(2)+0.25(2)+0.20(2)+0.15(3)+0.10(3).$$ That is $$L=0.60+0.50+0.40+0.45+0.30=\mathrm{2.25.}$$ The entropy of the source is 2.2282 bits, so the code sits 0.0218 bits above the floor. Section 16.4 says the optimal prefix code has average length at least the entropy and less than one bit above it, and Huffman reaches that optimum. The two least probable symbols receive the longest strings, which is the exchange argument in one line.

With $m=200$ and $H=1.5$, the typical set holds about $$2^{mH}=2^{200(1.5)}=2^{300}$$ sequences. Naming one of them takes about 300 bits. A fixed-length code for the same block would need $$200{\log }_{2}4=200(2)=400$$ bits, because each of the 200 positions has four possibilities. The typical-set code saves $$400-300=100$$ bits, a quarter of the fixed-length string. Section 16.5 says the saving comes from the shape of the distribution: the unlikely sequences exist, but they carry so little total probability that a code can leave most of them unnamed and accept a negligible risk of loss.

The noise entropy is $$H(0.25)=-0.25{\log }_{2}0.25-0.75{\log }_2\mathrm{0.75.}$$ The two terms are $$0.25(2)=0.5,0.75(0.4150)=0.3113,$$ so $$H(0.25)=\mathrm{0.8113.}$$ The capacity is $$C=1-H(0.25)=1-0.8113=\mathrm{0.1887.}$$ The naive guess $1-0.25=0.75$ assumes that the receiver knows which bits were flipped. It does not: it sees a bit and must decide whether to trust it, and the uncertainty about a flip is $H(0.25)$, not 0.25. Section 16.6 says rates below 0.1887 bits per use are achievable with long blocks, and rates above it are not. The channel is worse than the raw error rate suggests.