= Entropy bound for a random-length binary string
{title2=$H(M)\le H(L)+\mathbb EL$}
For a random finite binary string $M$ of length $L$, conditioning on $L=\ell$ leaves at most $2^\ell$ possible strings. Thus its <conditional entropy> is at most $\ell$. Since the length is a function of the string, the <chain rule for information entropy> gives
$$
H(M)=H(L)+H(M\mid L)\le H(L)+\mathbb EL.
$$
The term $H(L)$ cannot generally be removed. For concatenations of $m$ words from a fixed finite <decipherable code> with maximum length $d$, it is at most $\log_2(md+1)$. <Decipherable code>[Decipherability] preserves the <Shannon entropy> of the source block. For an independent source block, dividing the resulting inequality by $m$ and taking $m\to\infty$ proves the <expected codeword length> is at least the one-symbol <Shannon entropy>.
Back to article page
