Past exam of the communication Theory course of the University of Oxford / 2010 / 2 / a

For finite-valued random vectors, write $p(x,y)=P(X=x,Y=y)$ and $p_Y(y)=P(Y=y)$. The conditional entropy is the average entropy of the posterior distributions:Equivalently, $H(X\mid Y)=-{\sum }_{x,y:p(x,y)>0}p(x,y){\log }_{2}p(x\mid y)$. Since $p(x,y)=p_Y(y)p(x\mid y)$, splitting the logarithm givesUse the usual convention $0{\log }_{2}0=0$ and omit conditionals at zero-probability outputs. The same identities hold for countable alphabets whenever the entropy sums are well-defined, without subtracting two infinite quantities.

Set $Z=g(X)$. Given $X$, the value of $Z$ is certain, so $H(Z\mid X)=0$. Applying the entropy identity in the two orders givesbecause conditional entropy is nonnegative. ConsequentlyA deterministic coarsening can merge distinguishable source outcomes, but cannot create additional Shannon entropy.