Universal Coding on Infinite Alphabets: Exponentially Decreasing Envelopes

Abstract

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 $\frac{1}{4\alpha \log e}{\log }^{2}n$. Then a coding strategy is proposed, with a Bayes redundancy equivalent to the maximin redundancy. At last, an adaptive algorithm is provided, whose redundancy is equivalent to the minimax redundancy

References in corpus (1)

• Coding on countably infinite alphabets

Cited by in corpus (6)

• About adaptive coding on countable alphabets
• Some Properties of Rényi Entropy over Countably Infinite Alphabets
• Universal Weak Variable-Length Source Coding on Countable Infinite Alphabets
• Large Alphabet Compression and Predictive Distributions through Poissonization and Tilting
• Universal Compression of Envelope Classes: Tight Characterization via Poisson Sampling
• Pattern Coding Meets Censoring: (almost) Adaptive Coding on Countable Alphabets