[IEEE Trans. on Information Theory, November 1997, pp. 2026-2028]
Existence of Optimal Prefix Codes for Infinite Source Alphabets
Tamás Linder, Vahid Tarokh, and Kenneth Zeger
Abstract
It is proven that for every random variable with a countably infinite
set of outcomes and finite entropy there exists an optimal prefix code
which can be constructed
from Huffman codes for truncated versions of the random variable,
and that the average lengths of any sequence of Huffman codes for the
truncated versions converge to that of the optimal code.
Also, it is shown that every optimal infinite code
achieves Kraft's inequality with equality.