1 About Adaptive Coding on Countable Alphabets §
Dominique Bontemps, Stéphane Boucheron, Élisabeth Gassiat · 2012
Abstract—This paper sheds light on adaptive coding with respect to classes of memoryless sources over a countable alphabet defined by an envelope function with finite and non-decreasing hazard rate (log-concave envelope distributions). 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 by Haussler and Opper (1997) and on a careful analysis of the performance of the ACcoding algorithm. The latter relies on non-asymptotic bounds for maxima of samples from discrete distributions with finite and non-decreasing hazard rate. Index Terms—countable alphabets, redundancy, adaptive compression, minimax.