 Optimal one-to-one binary code

Suppose one source message is transmitted with its endpoint supplied externally, and allow the empty word. List source symbols in decreasing order of probability, $p_1\ge p_2\ge \cdots$, and assign distinct binary words in increasing length order. Then the $i$th word has length $\lfloor {\log }_{2}i\rfloor$, minimizing expected codeword length among one-to-one source codes.^[ref]

There are $1+2+\cdots +2^{\ell }=2^{\ell +1}-1$ binary words of length at most $\ell$. This proves the length formula. If a more probable symbol had a longer word than a less probable one, exchanging the two would decrease or preserve the expected value of the length, proving optimality.

For probabilities $(1/2,1/4,1/4)$, use the empty word, 0 and 1. The average is $1/2$ bit, compared with $3/2$ bits for an optimal binary prefix code. The difference uses the supplied endpoint: the three-word assignment cannot decode an arbitrary concatenated message stream without framing information.