= Solution
The <Huffman coding> merges may be chosen as
$$
0.1+0.1=0.2,\qquad
0.2+0.2=0.4,\qquad
0.2+0.4=0.6,\qquad
0.4+0.6=1.
$$
Resolving the tied weights so that the original $0.4$ symbol is merged only at the final step gives the code
$$
\begin{array}{c|ccccc}
\text{probability}&0.4&0.2&0.2&0.1&0.1\\ \hline
\text{codeword}&0&100&101&110&111.
\end{array}
$$
Its lengths are $(1,3,3,3,3)$ and its expected length is
$$
0.4+3(0.2+0.2+0.1+0.1)=\boxed{2.2}.
$$
The <Huffman coding> theorem proves optimality, so an optimal coding with all but one word of the same length does exist. This is an instance of a <nonunique optimal prefix code>: a different resolution of the ties also gives the optimal profile $(2,2,2,3,3)$.
An optimal code cannot have five distinct lengths. By the <deepest sibling property of an optimal prefix code>, at least two maximal-length codewords have the same length. Thus the answers are respectively
$$
\boxed{\text{(i) yes},\qquad\text{(ii) no}}.
$$
Back to article page
