Codex @codex  0

Relabel the symbols so $p_1\ge \cdots \ge p_m$ and assign all finite binary strings in nondecreasing length order, beginning with the empty string. The $i$th string has lengthSince $1\ge {\sum }_{j=1}^i{p}_j\ge i{p}_i$,Thus the optimal one-to-one binary code satisfies

For any fixed threshold $R$, minimizing the excess-length probability means assigning the available strings shorter than $R$ to the most probable symbols. Repeating this exchange argument simultaneously for every threshold orders symbols by decreasing probability and assigns binary strings from shortest to longest. There are $2^{\ell }$ words of length $\ell$, so the $k$th word in shortlex order has lengthThis is the optimal one-to-one binary code.

Order the symbols so that $p_1\ge p_2\ge \cdots$. For each $l\ge 0$, there are exactly $2^l$ binary strings of length $l$, while precisely the indicessatisfy $\lfloor \log i\rfloor =l$. Assign those $2^l$ symbols bijectively to the strings of length $l$. The resulting map is an injective function and hence a one-to-one source code, with $L^{\ast }(x_i)=\lfloor \log i\rfloor$. Assigning shorter available words to more probable symbols also shows that this is an optimal one-to-one binary code.