Monotonicity of expected empirical relative entropy ($\mathbb{E}D({\hat{p}}_{n+1}\Vert p)\le \mathbb{E}D({\hat{p}}_n\Vert p)$)

For independent and identically distributed observations from a probability mass function $p$ on a finite alphabet, expected relative entropy of the empirical distribution from $p$ is nonincreasing in sample size. The leave-one-out identity for empirical distributions and convexity of relative entropy in its first argument giveEvery deletion sample has the law of $n$ observations from $p$. Taking expected values proves the assertion without requiring independence between deletion samples. Zero-probability symbols are absent almost surely. Since $\mathbb{E}{\hat{p}}_n=p$, the identity $\mathbb{E}D({\hat{p}}_n\Vert p)=H(p)-\mathbb{E}H({\hat{p}}_n)$ also shows that expected empirical information entropy increases towards the source information entropy. Convergence follows from the strong law of large numbers for empirical frequencies and boundedness and continuity of information entropy on a finite probability simplex.