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

For probability mass functions on the finite alphabet, take logarithms to base two and define the relative entropy byA term with $q_i=0$ is zero, including $p_i=0$; a term with $q_i>0=p_i$ is $+\infty$. Fix $p_i>0$ and write $f_i(t)=t{\log }_2(t/p_i)$. For $t>0$,Thus $f_i$ is a convex function on $[0,\infty )$ by continuous extension to zero. For $0\le \lambda \le 1$, applying this scalar convexity to each coordinate and summing provesIf $p$ has zero coordinates, the finite-valued domain consists of probability mass functions supported on $\{i:p_i>0\}$; it is convex and the same proof applies there. Outside that domain the right side is infinite whenever an offending probability mass function has a positive mixture weight, so the extended-valued convexity assertion still holds. At mixture weights zero or one the inequality is an identity, without needing the expression $0\cdot \infty$.

Index correction: the printed definition only permits $i\le n$, although the required average includes $i=n+1$. Extend the same deletion formula to $1\le i\le n+1$. Without that extension the final summand is undefined; there is no new sample or different estimator to supply.

For a fixed outcome of the sample and a fixed symbol $x$, put $A_j=1_{\{X_j=x\}}$. The leave-one-out empirical distribution then satisfiesDividing by $n+1$ gives ${\hat{p}}_{n+1}=(n+1{)}^{-1}{\sum }_{i=1}^{n+1}{\hat{q}}_{n,i}$. Each of the $n+1$ indicator functions was counted exactly $n$ times before division by $n$. This leave-one-out identity for empirical distributions is deterministic; independence plays no part in this part.

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.