= Monotonicity of expected empirical relative entropy
{title2=$\mathbb E D(\widehat p_{n+1}\|p)\leq\mathbb E D(\widehat p_n\|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> give
$$
D(\widehat p_{n+1}\|p)\leq\frac1{n+1}\sum_{i=1}^{n+1}D(\widehat q_{n,i}\|p).
$$
Every 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\widehat p_n=p$, the identity $\mathbb E D(\widehat p_n\|p)=H(p)-\mathbb E H(\widehat 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>.
Back to article page
