From the archives
Coding on countably infinite alphabets
Historical material. Affiliations, schedules and roles on this page describe their original context.
JournalName: IEEE Transactions on Information Theory
Date: January, 2009
PageStart: 358
PageEnd: 373
Arxiv Number: 0801.2456
Hal Number: 00121892
Authors: Stéphane BoucheronAurélien GarivierElisabeth Gassiat
Abstract: This paper describes universal lossless coding strategies for
compressing sources on countably infinite alphabets. Classes of memoryless sources defined
by an envelope condition on the marginal distribution provide benchmarks for coding
techniques originating from the theory of universal coding over finite alphabets. We prove
general upper bounds on minimax regret and lower bounds on minimax redundancy for such
source classes. The general upper bounds emphasize the role of the normalized maximum
likelihood (NML) codes with respect to minimax regret in the infinite alphabet context.
Lower bounds are derived by tailoring sharp bounds on the redundancy of Krichevsky-Trofimov
coders for sources over finite alphabets. Up to logarithmic (resp., constant) factors the
bounds are matching for source classes defined by algebraically declining (resp.,
exponentially vanishing) envelopes. Effective and (almost) adaptive coding techniques are
described for the collection of source classes defined by algebraically vanishing envelopes.
Those results extend our knowledge concerning universal coding to contexts where the key
tools from parametric inference are known to fail.
Direct link: available on IEEE Xplore
Issue: 1
Volume: 55
Keywords:
