Skip to Main content Skip to Navigation
Journal articles

A Lower-Bound for the Maximin Redundancy in Pattern Coding

Abstract : We show that the maximin average redundancy in pattern coding is eventually larger than 1.84 (n/log n)(1/3) for messages of length n. This improves recent results on pattern redundancy, although it does not fill the gap between known lower- and upper-bounds. The pattern of a string is obtained by replacing each symbol by the index of its first occurrence. The problem of pattern coding is of interest because strongly universal codes have been proved to exist for patterns while universal message coding is impossible for memoryless sources on an infinite alphabet. The proof uses fine combinatorial results on partitions with small summands.
Complete list of metadata

https://hal-imt.archives-ouvertes.fr/hal-00479585
Contributor : Admin Télécom Paristech Connect in order to contact the contributor
Submitted on : Friday, April 30, 2010 - 9:28:54 PM
Last modification on : Wednesday, April 27, 2022 - 5:02:22 PM

Links full text

Identifiers

Collections

Citation

Aurélien Garivier. A Lower-Bound for the Maximin Redundancy in Pattern Coding. Entropy, MDPI, 2009, 11 (4), pp.634-642. ⟨10.3390/e11040634⟩. ⟨hal-00479585⟩

Share

Metrics

Record views

59