About Optimal Prefix Codes over Countably Infinite Alphabets: Probabilistic Intervals for the Codeword Lengths Assignment
This provides theoretical insights into optimal prefix codes for infinite alphabets, offering a simpler verification criterion for a specific code length pattern.
The paper proves that for discrete memoryless sources with countably infinite alphabets, there exist probability intervals where the optimal codeword length for the most probable symbol equals a given integer k, and provides a criterion for distributions where optimal code lengths follow the pattern l_i = i, requiring less information than existing methods.
For the discrete memoryless sources with a countably infinite alphabet, we prove that for any positive integer $k$, there exists a corresponding probability interval such that if the largest symbol probability $p_{1}$ falls in this interval, the optimal code length for the symbol equals $k$. Furthermore, for infinite sources, we provide a criterion to determine probability distributions whose optimal code length assignment follows the pattern $l^{best}_{i}=i$, for $i\ge 1$. Compared with the existing conclusion for anti-uniform sources, the proposed criterion requires less information for verification.