= Mismatch penalty in lossless coding
{title2=$\mathbb E_P[\ell(X)]=H(P,Q)$}
Suppose a binary <prefix code> has integer <codeword lengths> $\ell_i=-\log_2 q_i$. Under a source with <probability mass function> $p_i$, its average <codeword length> is exactly <cross-entropy>, $\sum_i p_i\ell_i=H(P,Q)$. The <Kraft inequality> is satisfied because $\sum_i2^{-\ell_i}=\sum_iq_i=1$. This exact interpretation requires suitable <dyadic rational> <probabilities>; a general $-\log_2q_i$ is not an integer <codeword length>. For positive $q_i$, a <prefix code> with lengths $\lceil-\log_2q_i\rceil$ exists by the <Kraft inequality> and has average length between $H(P,Q)$ and $H(P,Q)+1$. The <ceiling function> causes the one-symbol rounding overhead. The cross-entropy term describes mismatch overhead; those are distinct costs.
Back to article page
