Past exam of the mathematics course of the University of Cambridge / 2024 / iii / Paper 208 / 2 / a / Solution

For $X^{(i)}=X_{1:n}\setminus X_i$, Han's inequality for relative entropy states that, when $P={⨂}_{i=1}^n{P}_i$,

First prove the chain rule for relative entropy. For two coordinates,Taking expectation under $Q$ givesand iteration proves the chain rule for any finite product.

Write $Q_i(\cdot \mid x_{<i})$ for the successive conditional distributions. Since $P$ is a product, the chain rule givesFor a fixed omitted coordinate $j$, applying the chain rule in the remaining coordinate order givesThe convexity of Kullback-Leibler divergence implies that removing $X_j$ from the conditioning can only decrease each averaged conditional divergence. Summing over $j$, each full conditional increment occurs for exactly the $n-1$ indices $j\ne i$, and thereforewhich is the claimed inequality. Equivalently, this is Han's entropy inequality after expanding each divergence: the product-reference cross-entropy terms cancel because they are modular.