Universal Coding on Infinite Alphabets: Exponentially Decreasing Envelopes.

This paper deals with the problem of universal lossless coding on a countable infinite alphabet. It focuses on some classes of sources defined by an envelope condition on the marginal distribution, namely exponentially decreasing envelope classes with exponent \alpha. The minimax redundancy of exponentially decreasing envelope classes is proved to be equivalent to 1 \over 4 \alpha \log e \log^2 n. Then, an adaptive algorithm is proposed, whose maximum redundancy is equivalent to the minimax redundancy. [ABSTRACT FROM PUBLISHER]