= Solution
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 length
$$
L^*(x_k)=\lfloor\log_2k\rfloor.
$$
This is the <optimal one-to-one binary code>.
Back to article page
