Past exam of the information theory course of the University of Oxford / 2021 / 1 / a

The chain rule for conditional entropy givesIndeed, for every conditioning value $(x,z)$ of positive probability, each summand $-p(y\mid x,z){\log }_{2}p(y\mid x,z)$ is nonnegative. Its sum is zero exactly when the conditional probability mass function is concentrated at one value. Averaging over $(X,Z)$ therefore proves both the inequality and its equality criterion: equality holds exactly when $Y=f(X,Z)$ almost surely for some function $f$. Conditioning values of probability zero impose no restriction. This is a statement about discrete random variables; a differential entropy need not be nonnegative.

Expand the two observations in order using the chain rule for mutual information:The remaining conditional mutual information isRelative entropy nonnegativity proves the inequality. Equality requires every positive-weight relative entropy to vanish, which is equivalent to $p(y,z\mid x)=p(y\mid x)p(z\mid x)$ for every $x$ of positive probability. Thus equality holds exactly when $Y$ and $Z$ have conditional independence given $X$. No unconditional independence is required.

The chain rule for information entropy converts the two differences into conditional entropies. Their gap, in the order right minus left, isThis is additional conditioning reduces entropy. The relative entropy representation of conditional mutual information identifies exactly when that gap vanishes: equality holds if and only if $Y$ and $Z$ have conditional independence given $X$. Knowledge of $Y$ then changes no conditional probability of $Z$ after $X$ is known.

Here the asserted bound is actually an identity, so equality always holds whenever the displayed quantities are defined. Expand the same mutual information in two orders:Equating these expressions and using symmetry of mutual information and conditional mutual information givesThere is no further independence condition. Treating this part as a strict inequality would obscure its cancellation.