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

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.

Define the tilted probability measure $Q$ by $dQ=ZdP$; this is normalized because $\mathbb{E}Z=1$. ThenLet ${\mathbb{E}}_i$ average only coordinate $i$, keeping $X^{(i)}$ fixed. The marginal density of $Q_{X^{(i)}}$ relative to $P_{X^{(i)}}$ is ${\mathbb{E}}_{i}Z$, and henceMoreover,Substituting Han's inequality for relative entropy and rearranging gives the tensorization of entropy

The chain rule, now separating $X_i$ first, giveswhere the second term denotes the conditional divergence averaged over $Q_{X_i}$. Summing over $i$ yieldsRepeated use of the chain rule and convexity gives the tensorization lower bound for relative entropyTherefore the preceding sum is at least $(n-1)D(Q\Vert P)$, which is equivalent to the required inequality.

Again put $dQ=ZdP$. With ${\mathbb{E}}^{[i]}Z=\mathbb{E}[Z\mid X_i]$, the conditional density of $Q_{X^{(i)}\mid X_i}$ relative to $P_{X^{(i)}}$ is $Z/{\mathbb{E}}^{[i]}Z$. ConsequentlyPart c now gives the alternative tensorization boundUnlike the bound in part b, each summand averages over all coordinates other than $i$ while holding $X_i$ fixed.

Yes. Write $D_S=D(Q_{X_S}\Vert P_{X_S})$ and $D=D_{\{1,\dots ,n\}}$. The bounds from b and d are respectivelyThe Strong form of Han's entropy inequality, obtained by repeated entropy submodularity, statesAfter replacing entropies by divergences from the product reference, whose cross-entropy terms cancel, this is exactly $B_{\mathrm{new}}\le B_{\mathrm{old}}$. Equality holds for product $Q$ and when $n=2$; dependence can make the new bound strictly smaller.