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/1 alpha log e log(2) n. Then, an adaptive algorithm is proposed, whose maximum redundancy is equivalent to the minimax redundancy.
universal coding redundancy adaptive compression bayes mixture data compression infinite countable alphabets