= Solution
\b[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\geq1$.
Under the consistent interpretation \b[$\rho=p$], the preceding <leave-one-out identity for empirical distributions> and <convexity of relative entropy in its first argument> give, for every sample,
$$
D(\widehat p_{n+1}\|p)
\leq\frac1{n+1}\sum_{i=1}^{n+1}D(\widehat q_{n,i}\|p).
$$
Deleting any one observation from $n+1$ <independent and identically distributed random variables> leaves $n$ <independent> observations with <probability mass function> $p$. Consequently each $\widehat q_{n,i}$ has the same distribution as $\widehat p_n$. They need not be <independent> of one another. Taking <expected values> and using <linearity of expectation> therefore proves
$$
\boxed{\mathbb E D(\widehat p_{n+1}\|p)\leq\mathbb E D(\widehat p_n\|p).}
$$
Zero 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\widehat p_n=p$ give the <expected relative entropy decomposition>
$$
\mathbb E D(\widehat p_n\|\rho)=\mathbb E D(\widehat p_n\|p)+D(p\|\rho).
$$
Thus the valid arbitrary-reference version has $\rho$ on \i[both] sides; the printed mixed-reference version has an additional term whose sign prevents the proposed conclusion.
Back to article page
