Past exam of the communication Theory course of the University of Oxford / 2007 / 2 / c / Solution

At an interior tree node write $A,B$ for the total masses in its two children, and $S=A+B$. Counting path lengths and telescoping the Shannon entropy over the binary decisions givesIndeed each symbol contributes its probability once per ancestral interior node to the first sum. In the second sum, expanding $Sh(A/S)=S{\log }_{2}S-A{\log }_{2}A-B{\log }_{2}B$ cancels the interior terms and leaves the source Shannon entropy. The supplied inequality now bounds redundancy byConsider the cut between adjacent symbols $k,k+1$ made at one node. If its left side is heavier, moving its last symbol to the right must not improve the chosen cut. Writing $\Delta =A-B\ge 0$, this says $|\Delta -2p_k|\ge \Delta$, which implies $\Delta \le p_k$; when the left side is a singleton the same bound is immediate. If the right side is heavier, the corresponding argument gives $|A-B|\le p_{k+1}$. In all casesRecursive subdivision of contiguous blocks uses each original gap exactly once. Summing over the $m-1$ gaps therefore givesproving $\bar{s}<H(X)+2$. If probabilities are already nonincreasing, each maximum is $p_k$ and the improved bound is $\bar{s}-H(X)\le 1-p_m<1$. Thus the sorted version has expected length less than $H(X)+1$, although it need not be optimal. For one symbol the assertions hold directly. This is the Fano slice code redundancy bound.