DOAJ Open Access 2012

Adaptive compression against a countable alphabet

Dominique Bontemps Stephane Boucheron Elisabeth Gassiat

Lihat Sumber DOI

Abstrak

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 by Haussler and Opper (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.

Topik & Kata Kunci

Mathematics

Penulis (3)

Dominique Bontemps

Stephane Boucheron

Elisabeth Gassiat

Format Sitasi

APA MLA BibTeX

Bontemps, D., Boucheron, S., Gassiat, E. (2012). Adaptive compression against a countable alphabet. https://doi.org/10.46298/dmtcs.2995

Akses Cepat

Lihat di Sumber doi.org/10.46298/dmtcs.2995

Informasi Jurnal

Tahun Terbit: 2012
Sumber Database: DOAJ
DOI: 10.46298/dmtcs.2995
Akses: Open Access ✓