About Adaptive Coding on Countable Alphabets

DOI10.1109/TIT.2013.2288914MaRDI QIDQ5346094zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Dominique Bontemps, Stéphane Boucheron, Elisabeth Gassiat

Publication date 8 June 2017

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1202.0258

Mathematics Subject Classification ID

Source coding (94A29)

Abstract: This paper sheds light on universal coding with respect to classes of memoryless sources over a countable alphabet defined by an envelope function with finite and non-decreasing hazard rate. We prove that the auto-censuring AC code introduced by Bontemps (2011) is adaptive with respect to the collection of such classes. The analysis builds on the tight characterization of universal redundancy rate in terms of metric entropy % of small source classes by Opper and Haussler (1997) and on a careful analysis of the performance of the AC-coding algorithm. The latter relies on non-asymptotic bounds for maxima of samples from discrete distributions with finite and non-decreasing hazard rate.

Cited in

(2)

• Alphabet cardinality and adaptive evolution
• Agafonov's theorem for finite and infinite alphabets and probability distributions different from equidistribution

This page was built for publication: About Adaptive Coding on Countable Alphabets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5346094)