Key points are not available for this paper at this time.
It is known that the expected codeword length Lₔ₃ of the best uniquely decodable (UD) code satisfies H (X) ₔ₃. Let X be a random variable which can take on n values. Then it is shown that the average codeword length L₁: ₁ for the best one-to-one (not necessarily uniquely decodable) code for X is shorter than the average codeword length Lₔ₃ for the best uniquely decodable code by no more than (₂ ₂ n) + 3. Let Y be a random variable taking on a finite or countable number of values and having entropy H. Then it is proved that L₁: ₁ H-₂ (H + 1) -₂₂ (H + 1) - -6. Some relations are established among the Kolmogorov, Chaitin, and extension complexities. Finally it is shown that, for all computable probability distributions, the universal prefix codes associated with the conditional Chaitin complexity have expected codeword length within a constant of the Shannon entropy.
Leung-Yan-Cheong et al. (Mon,) studied this question.