Past exam of the communication Theory course of the University of Oxford / 2008 / 4 / b

The redundancy is $R=\bar{\ell }-H(X)$, measured in bits per source symbol. Write $s_v={\sigma }_0(v)+{\sigma }_1(v)$ for the total mass passing through interior node $v$. Counting each codeword's length as one for each interior node its route visits givesThe entropy can be split into the conditional binary decisions along that route. Algebraically each node contributesSumming telescopes: each non-root interior mass appears once positively as a parent and once negatively as a child. The root term is $1{\log }_{2}1=0$ and the remaining leaf terms sum to $-{\sum }_x{p}_x{\log }_2{p}_x=H(X)$. HenceSubtracting this identity from the expected-length identity provesThus redundancy is the sum of the probability-weighted imbalances of the binary branch decisions. Nodes with no mass contribute zero by continuity. The formula holds for every full prefix tree, even without optimality.