Past exam of the information theory course of the University of Oxford / 2023 / 2 / b

For a fixed estimated probability mass function $q$, the estimated joint probability mass function is $q_n(x_1,\dots ,x_n)={\prod }_{i}q(x_i)$. If $q(x)>0$ whenever $p(x)>0$, the strong law of large numbers gives the mismatched asymptotic equipartition property:Here $H(p,q)$ is cross-entropy, and the last equality is cross-entropy equals entropy plus relative entropy. The Kullback-Leibler divergence measures the extra average logarithmic loss from the estimated law.

If $q(x)=0$ for some $x$ with $p(x)>0$, let $a={\sum }_{x:q(x)=0}p(x)>0$. The probability that none of the first $n$ observations belongs to this set is $(1-a{)}^n\to 0$. Almost surely such a symbol eventually occurs, after which $q_n(X_1,\dots ,X_n)=0$ forever. Thus the limit is $-\infty$, consistent with infinite cross-entropy and infinite Kullback-Leibler divergence.