Past exam of the information theory course of the University of Oxford / 2021 / 1 / b / iii / Solution

Reference-distribution ambiguity: $\rho$ is not defined in the paper. If it is an arbitrary probability mass function, the printed inequality is false. For instance, choose $p=(1,0)$ and $\rho =(1/2,1/2)$. Every empirical distribution equals $p$, making the printed left side one bit and its right side zero. This is a counterexample for every $n\ge 1$.

Under the consistent interpretation $\rho =p$, the preceding leave-one-out identity for empirical distributions and convexity of relative entropy in its first argument give, for every sample,Deleting any one observation from $n+1$ independent and identically distributed random variables leaves $n$ independent observations with probability mass function $p$. Consequently each ${\hat{q}}_{n,i}$ has the same distribution as ${\hat{p}}_n$. They need not be independent of one another. Taking expected values and using linearity of expectation therefore provesZero coordinates of $p$ are never sampled, almost surely, so the calculation can be restricted to its probability support. In particular the expected values are finite on this finite alphabet.

The discrepancy cannot be removed by silently choosing any fixed reference. Whenever $\rho$ is positive on the probability support of $p$, direct subtraction and $\mathbb{E}{\hat{p}}_n=p$ give the expected relative entropy decompositionThus the valid arbitrary-reference version has $\rho$ on both sides; the printed mixed-reference version has an additional term whose sign prevents the proposed conclusion.