= Solution
For the direct half of the <code-distribution correspondence>, let $L$ be the length function of a binary prefix code and put
$$
K=\sum_x2^{-L(x)}\leq1,
\qquad
R(x)=\frac{2^{-L(x)}}K.
$$
Then $R$ is a <probability mass function> and
$$
-\log_2R(x)=L(x)+\log_2K\leq L(x).
$$
Thus every prefix code determines a distribution whose ideal description lengths do not exceed the codeword lengths.
Conversely, given a probability mass function $R$, set
$$
L(x)=\left\lceil-\log_2R(x)\right\rceil
$$
for $R(x)>0$. Then $2^{-L(x)}\leq R(x)$, so the <Kraft inequality> is satisfied. Its converse supplies a binary prefix code with these lengths, and
$$
-\log_2R(x)\leq L(x)<-\log_2R(x)+1.
$$
If real lengths are allowed, the ideal choice $L(x)=-\log_2R(x)$ satisfies Kraft with equality.
Back to article page
